Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 17.01.2009, 19:18
ugo ugo вне форума
Новичок

Отправить личное сообщение для ugo Посмотреть профиль Найти все сообщения от ugo
 
Регистрация: 17.01.2009
Сообщений: 19

Я правильно понимаю что таким способом мы сгенерируем сами разбиения, а не только посчитаем их число?
  #12  
Старый 17.01.2009, 19:38
гость

 
Сообщений: n/a

Сообщение от ugo Посмотреть сообщение
Я правильно понимаю что таким способом мы сгенерируем сами разбиения, а не только посчитаем их число?
Таким способом считается их число.

Сгенерировать можно и простой рекурсией.
  #13  
Старый 17.01.2009, 21:52
ugo ugo вне форума
Новичок

Отправить личное сообщение для ugo Посмотреть профиль Найти все сообщения от ugo
 
Регистрация: 17.01.2009
Сообщений: 19

Если сгенерировать их проще, чем подсчитать кол-во, то мне подойдет и сама генерация. Буду очень благодарен если вы расскажете как)
  #14  
Старый 17.01.2009, 22:34
гость

 
Сообщений: n/a

Код на Питоне:
Код:
def generate_multi_partitions(values, K, func):
    N = len(values)
    values = sorted(values)
    avail = [True for each in range(N)]
    output = [[] for each in range(K)]

    def foo(k):
        if k == K-1:
            output[k] = []
            for i in range(N):
                if avail[i]:
                    output[k].append(values[i])
            if len(output[k]) > 0:
                func(output)
        else:
            for i in range(N):
                if avail[i]:
                    bar(k, i)
                    return

    def bar(k, i):
        output[k].append(values[i])
        avail[i] = False
        foo(k+1)
        for j in range(i+1, N):
            if avail[j]:
                bar(k, j)
        output[k].pop()
        avail[i] = True

    foo(0)

Пример работы:
Код:
import sys
generate_multi_partitions([1,2,2,3,4], 2, lambda p: sys.stdout.write('%s\n' % p))
Код:
[[1], [2, 2, 3, 4]]
[[1, 2], [2, 3, 4]]
[[1, 2, 2], [3, 4]]
[[1, 2, 2, 3], [4]]
[[1, 2, 2, 4], [3]]
[[1, 2, 3], [2, 4]]
[[1, 2, 3, 4], [2]]
[[1, 2, 4], [2, 3]]
[[1, 2], [2, 3, 4]]
[[1, 2, 3], [2, 4]]
[[1, 2, 3, 4], [2]]
[[1, 2, 4], [2, 3]]
[[1, 3], [2, 2, 4]]
[[1, 3, 4], [2, 2]]
[[1, 4], [2, 2, 3]]
  #15  
Старый 17.01.2009, 22:40
гость

 
Сообщений: n/a

Упс, маленькая поправка, на строке 26 должно быть:
Код:
if avail[j] and (j == 0 or values[j-1] != values[j] or not avail[j-1]):
Тогда вывод для примера:
Код:
[[1], [2, 2, 3, 4]]
[[1, 2], [2, 3, 4]]
[[1, 2, 2], [3, 4]]
[[1, 2, 2, 3], [4]]
[[1, 2, 2, 4], [3]]
[[1, 2, 3], [2, 4]]
[[1, 2, 3, 4], [2]]
[[1, 2, 4], [2, 3]]
[[1, 3], [2, 2, 4]]
[[1, 3, 4], [2, 2]]
[[1, 4], [2, 2, 3]]
  #16  
Старый 18.01.2009, 00:29
ugo ugo вне форума
Новичок

Отправить личное сообщение для ugo Посмотреть профиль Найти все сообщения от ugo
 
Регистрация: 17.01.2009
Сообщений: 19

огромное спасибо
  #17  
Старый 18.01.2009, 01:41
ugo ugo вне форума
Новичок

Отправить личное сообщение для ugo Посмотреть профиль Найти все сообщения от ugo
 
Регистрация: 17.01.2009
Сообщений: 19

По-моему для values={3,3,3} и K=2 программа выведет 2 раза одно разбиение.
[3],[3,3]
[3,3],[3]
  #18  
Старый 18.01.2009, 01:47
гость

 
Сообщений: n/a

Да, действительно. Я подумаю как это пофиксить.
  #19  
Старый 18.01.2009, 02:05
гость

 
Сообщений: n/a

Предлагаю следующий фикс - заменить функцию foo() на:
Код:
    def foo(k):
        if k >= 2 and output[k-2] > output[k-1]:   # (лексикографическое сравнение списков)
            return
        if k == K-1:
            output[k] = []
            for i in range(N):
                if avail[i]:
                    output[k].append(values[i])
            if len(output[k]) > 0 and (k == 0 or output[k-1] <= output[k]):
                func(output)
            output[k] = []
        else:
            for i in range(N):
                if avail[i]:
                    bar(k, i)
                    return
Теперь все подмножества в разбиении генерятся строго в лексикографическом порядке (что можно считать канонической формой для разбиений), и повторяющихся разбиений теперь быть не должно.
  #20  
Старый 18.01.2009, 02:18
ugo ugo вне форума
Новичок

Отправить личное сообщение для ugo Посмотреть профиль Найти все сообщения от ugo
 
Регистрация: 17.01.2009
Сообщений: 19

Кажется теперь все работает, еще раз большое спасибо)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение множества элементарных циклов графа kilobait Графы 9 17.03.2008 10:02
Покрытие множества кругами Tolran Вычислительная геометрия 3 29.11.2007 01:00
алгоритм нахождения минимального множества сечений контуров обратной связи ikro Графы 0 03.05.2007 11:00
разбиение плоскости фигурами ASH Вычислительная геометрия 1 17.03.2007 15:13
разбиение прямоугольника helium Вычислительная геометрия 5 03.03.2007 11:24