Рекурсия - Как сгенерировать все последовательности с заданными n и k - PullRequest
Новая
       24

Рекурсия - Как сгенерировать все последовательности с заданными n и k

0 голосов
/ 25 ноября 2018

Учитывая n и k, мне нужно сгенерировать все следующие последовательности: 

n=5, k=2
0,1,2
0,1,3
0,1,4
1,2,3
1,2,4
2,3,4

Другой пример: 

n=5, k=3
0,1,2,3
0,1,2,4
0,1,3,4
0,2,3,4
1,2,3,4

Я думаю, что это можно решить с помощью рекурсии, но получилзастрял.Нужна помощь

1 Ответ

0 голосов
/ 25 ноября 2018

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

  1. Каждая комбинация c будет списком;[0,1,2], [0,1,3] и т. Д. Мы инициализируем пустую комбинацию как c = [], пустой список.Когда мы зациклимся, «выбранные» значения будут добавлены к нашей комбинации.

  2. Мы хотим выбрать k значения.Если k меньше нуля, мы не можем добавить больше значений к нашей комбинации c.Выведите комбинацию.

  3. Выбранные значения начнутся с 0, считая до n.Мы представим текущее значение с помощью m и инициализируем его нашим начальным значением, m = 0.Прекратите генерировать значения, если m равно n

  4. . Начните с выбора m.Делать выбор - значит уменьшать k на единицу.Выбор также означает добавление его в нашу комбинацию с помощью c + [m].Следующий выбор будет m + 1.

  5. Далее, мы делаем , а не выбираем m.Отказ от выбора означает, что k не уменьшен.Наша комбинация c остается прежней.Перейти к следующему значению m + 1.

Код в основном пишет сам сейчас 

def combnk (n, k, m = 0, c = []):                 # 1
  if k < 0:
    yield c                                       # 2
  elif n == m:
    return                                        # 3
  else:
    yield from combnk (n, k - 1, m + 1, c + [m])  # 4
    yield from combnk (n, k    , m + 1, c      )  # 5

print (list (combnk (5, 2)))
# [ [0, 1, 2]
# , [0, 1, 3]
# , [0, 1, 4]
# , [0, 2, 3]
# , [0, 2, 4]
# , [0, 3, 4]
# , [1, 2, 3]
# , [1, 2, 4]
# , [1, 3, 4]
# , [2, 3, 4]
# ]

print (list (combnk (5, 3)))
# [ [0, 1, 2, 3]
# , [0, 1, 2, 4]
# , [0, 1, 3, 4]
# , [0, 2, 3, 4]
# , [1, 2, 3, 4]
# ]
...