Вычисление комбинаций длины k из списка длины n с использованием рекурсии

Question

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

Например:

INPUT:  choose_sets([1,2,3,4],3)
OUTPUT: [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

INPUT:  choose_sets([1,2,3,4],2)
OUTPUT: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Я застрял в реализации этого в коде, поэтому я был бы рад за некоторую помощь.Пока это мой код (я что-то упускаю, просто не знаю что):

def choose_sets(lst,k):

    if k == len(lst):
        return lst
    if k == 0:
        return []
    if k > len(lst):
        return []

    sets=[]
    sub_lst=lst[:]
    sub_lst.remove(sub_lst[0])

    a= choose_sets(sub_lst,k-1)
    for i in a:
        i.append(lst[0])
    sets.append(a)

    b= choose_sets(sub_lst,k)
    sets.append(b)


    return sets

Answer 1

Вы можете получить решение от Генератор для перестановок, комбинаций, выбора последовательности (рецепт Python)

def xuniqueCombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in xuniqueCombinations(items[i+1:],n-1):
                yield [items[i]]+cc



>>> def xuniqueCombinations(items, n):
...     if n==0: yield []
...     else:
...         for i in xrange(len(items)):
...             for cc in xuniqueCombinations(items[i+1:],n-1):
...                 yield [items[i]]+cc
... 
>>> for x in xuniqueCombinations( [1,2,3,4],2):
...     print x
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

Отредактировано 4 года спустя (7/12/2015)

Чтобы запустить его на Python3, просто измените xrange на range, Диапазон Python3 - это xrange Python2. .Спасибо @ ederollora за то, что заметили меня.

Answer 2

Это на Java, и я не могу гарантировать, что он работает на 100% должным образом, но, похоже, быстрое создание прототипов работает нормально.Надеюсь, это поможет в любом случае.

public void choose_sets(int values[], int count) {
    int perm[] = new int[count];
    choose_sets(values, 0, perm, 0, count);
}

public void choose_sets(int[] values, int valuesIdx, int[] perm,
                        int permIdx, int count) {
    if (permIdx == count) {
        // At this point perm -array contains single permutation
        // of length ´count´.
    } else {
        for (int i = valuesIdx; i < values.length; ++i) {
            perm[permIdx] = values[i];
            choose_sets(values, i + 1, perm, permIdx + 1, count);
        }
    }
}

Answer 3

в основном вам нужно использовать следующую рекурсию:

f (k, n) = append_to_each (f (k-1, n-1), n) |f (k, n-1)

def combinations(lst,k):
    n = len(lst)
    if n == k:
        return [set(lst)]
    if k == 1:
        return [set([lst[i]]) for i in range(n)]
    v1 = combinations(lst[:-1], k-1)
    v1new = [ i.add(lst[n-1]) for i in v1]
    v2 = combinations(lst[:-1], k)
    return v1+v2

Answer 4

Вы почти у цели, только несколько незначительных вещей. Алгоритм в основном правильный, но

if k == len(lst):
    return lst

Это неправильный тип. Тип возвращаемого значения - это не список вещь , а список (список вещь ), поэтому он должен быть

if k == len(lst):
    return [lst]

Далее

if k == 0:
    return []

Каждый список имеет ровно один непустой подсписок, пустой список, так что должно быть

if k == 0:
    return [[]]

Для остальных

if k > len(lst):
    return []

полностью правильно.

sets=[]
sub_lst=lst[:]
sub_lst.remove(sub_lst[0])

Это правильно, но можно выразить более кратко, как

sub_lst = lst[1:]

Теперь еще один тип смешивания:

a= choose_sets(sub_lst,k-1)
for i in a:
    i.append(lst[0])
sets.append(a)

То, что sets.append(a) помещает a в один слот из sets, вы хотите объединить два списка, sets = sets + a. И если вам нужны комбинации в порядке, в котором элементы появляются в списке, вместо i.append(lst[0]), вы должны добавить [lst[0]] + i к sets в цикле, но это вопрос склонности.

b= choose_sets(sub_lst,k)
sets.append(b)

Опять не добавляйте, а объединяйте здесь,

sets = sets + b

Answer 5

Посмотрите на это решение:

def choose_sets(mylist,length):
    mylen = len(mylist)

    if length == mylen:
        return [mylist]
    if length == 1:
        return [[i] for i in mylist]
    if length > mylen:
        return []

    ToRet = []
    for k in xrange(mylen): 
        if mylen - k + 1> length :
            for j in choose_sets(mylist[k+1:],length-1):
                New = [mylist[k]]
                New.extend(j)
                ToRet.append(New)
    return ToRet

print choose_sets([1,2,3,4,5],3)

Есть более элегантные способы, но это должно быть хорошо, как домашнее задание ...