Печатайте комбинации n-длины без повторений, используя рекурсию

Question

В дополнение к этой проблеме: Печать комбинаций n-длины из списка символов с использованием рекурсии

Теперь я должен реализовать тот же алгоритм с другим поворотом: без повторений некоторого символа.

Реализовать в Python функцию, которая получает в виде параметров список символов и целое число n.Функция должна печатать все возможные комбинации длины n, где каждый символ может быть показан только один раз.

Так как я новичок и плохо в рекурсии, я неУспешно придумать элегантное решение, чтобы решить эту проблему.

Я думал использовать тот же код из предыдущей задачи:

def print_sequences(char_list, n, _accum=[]):
  if len(_accum) == n:
    print(_accum)
  else:
    for c in char_list:
      print_sequences(char_list, n, _accum+[c])

И просто создать новую функцию (return_without_repetition), которая принимаетсписок и проходит по нему, создает новый список без повторений.Так, что когда я печатаю список, я использую функцию:

if len(_accum) == n:
    print(return_without_repetition(_accum))

Но это очень неэффективно и не элегантно.

Может быть, есть другой способ решить эту проблему путем определения новых списков втело рекурсии, но я заблудился относительно области видимости и подходящих мест для определения списков ...

Answer 1

Эта проблема - фактически все неповторяющиеся перестановки размера k.Вот его легко читаемая версия:

def permutations(items, k):
   def f(path):
      if len(path) == k:
         print(path)
         return
      else:
         for item in items:
             if item not in path:
                 f(path + [item])
      f([])

Вызов этой функции дает:

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

Answer 2

Изменение логики в ответе @ Ajax1234 в связанном вопросе, чтобы просто пропустить итерацию цикла for, если повторение значения в списке _accum будет выглядеть следующим образом:

def print_sequences(char_list, n, _accum=[]):
    if len(_accum) == n:
        print(_accum)
    else:
        for c in char_list:
            if c in _accum:
                continue
            print_sequences(char_list, n, _accum+[c])

print_sequences([1, 2, 3, 4], 4)

В соответствии с этим объяснением комбинаций и перестановок мы можем рассчитать ожидаемое количество результатов, используя 4 !, то есть 24. (Эта же ссылка на странице объясняет, почему 4 ⁴ или 256, - ожидаемое количество результатов в ответе на ваш предыдущий вопрос)

При ответе выше будут распечатаны следующие 24 списка результатов:

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