Почему эта модифицированная функция декартова произведения для Python не работает?

В идеале ввод — это [1,2], а вывод — все комбинации [[1,1], [2,2], [1,2], [2,1]]. В общем, выведите все возможные комбинации с заменой.

def cart(lst):
   if lst == []:
      return [[]]

   return [x[i:] + [lst[0]] + x[:i] for x in cart(lst[1:]) for i in range(len(x)) ]

l = [1,2,3] 
print cart(l)

Возвращает

[]

В более удобочитаемой форме код в основном говорит:

for x in cart(lst[1:]):
   for i in range(len(x)):
      return x[i:] + [lst[0]] + x[:i]

И если мы предположим рекурсивный случай с вводом [1,2,3], то cart([2,3]) должен произвести [[2,3], [3,2], [2,2], [3,3]], и поэтому для рекурсивного шага мы хотели бы вставить 1 во все возможные места. (В этом коде может отсутствовать регистр 111.)

Код кажется логически правильным, но выводит пустую строку.

Чего-то не хватает или я неправильно подхожу к проблеме?

Изменить

На самом деле я понимаю, что код будет немного сложнее:

def cart(lst):
    if len(lst) <= 1:
        return lst
    else:
        return [x[i:] + [lst[j]] + x[:i] for x in cart(lst[1:]) for j in range(len(lst)) for i in range(len(x))]

Хотя это по-прежнему странно возвращает пустой список. Я подозреваю, что мне не хватает базового случая.

Изменить

Это как-то связано с моим базовым случаем. Пересмотренный код:

def cart(lst):
    if len(lst) <= 1:
        return [lst]
    else:
        return [x[i:] + [lst[j]] + x[:i] for x in cart(lst[1:]) for j in range(len(lst)) for i in range(len(x))]

l = [1,2,3]
print cart(l)

Но теперь возвращается

[[3, 2, 1], [2, 1, 3], [3, 2, 2], [2, 2, 3], [3, 2, 3], [2, 3, 3], [3, 3, 1 ], [3, 1, 3], [3, 3, 2], [3, 2, 3], [3, 3, 3], [3, 3, 3]]

Уже лучше, хотя на выходе наборы отсутствуют. Похоже, снова проблема с базовым случаем.


python product cartesian
person Aspen    schedule 11.02.2016    source источник
comment
Если вы нашли ответ на свой вопрос, то опубликуйте его как таковой и примите его. Это выгодно всем.   -  person Vincent Savard    schedule 11.02.2016
comment
Итак, вы хотите внедрить itertools.product?   -  person Copperfield    schedule 11.02.2016
comment
в этом случае вы можете изучить его в документации, там есть чистая версия Python, вы можете использовать ее или какую-то ее вариацию на свой вкус   -  person Copperfield    schedule 11.02.2016

Ответы (1)


arrow_upward
0
arrow_downward

Нашел ответ здесь Алгоритм рекурсивной функции для перестановок с заменой на питоне

def permutations_with_replacement(k,n):
         # special case (not part of recursion)
         if k == 0:
            return []

         if k == 1:
            return [[n[i]] for i in range(len(n))]

         else:
            # Make the list by sticking the k-1 permutations onto each number 
            # we can select here at level k    
            result = []
            # Only call the k-1 case once, though we need it's output n times.
            k_take_one_permutations = permutations_with_replacement(k-1,n)  

            for i in range(len(n)):
                for permutation in k_take_one_permutations:
                    result.append([n[i]]+permutation)   
            return result

         print permutations_with_replacement(3,2)

print permutations_with_replacement(3, [1,2,3])

Похоже, я пытался взять рекурсивный случай самого списка, а не размер комбинаций.

Мне интересно, будет ли решение выполнимо повторением в списке, а не размером комбинаций.

person Aspen    schedule 11.02.2016