finding all the posible k-length lists from n elements

[ni5958]

Hi,
i need to write a recursive function which gets a list and an integer k and returns a list of all the possibilities of creating sub lists to the length of k with the elements from the original list.
i hope i was clear enough..
here are some examples:
>>> choose_sets([1,2,3, 4],0)
[[]]
>>> choose_sets([1,2,3, 4],2)
[[2, 1], [3, 1], [4, 1], [3, 2], [4, 2], [3, 4]]
>>> choose_sets([1,2,3, 4],4)
[[1, 2, 3, 4]]
>>> choose_sets(,4)
[['d', 'c', 'b', 'a'], ['e', 'c', 'b', 'a'], ['d', 'e', 'b', 'a'], ['c', 'd', 'e', 'a'], ['b', 'c', 'd', 'e']]

i've already thought of an easy way to solve it :

def choose_sets_help(lst, k,ans):
    ''' Input: lst,
        Output: a list of all k-length sub-lists '''
    if len(lst)==k :
        if lst not in ans:
            ans.append(lst)
        return ans
    if len(lst)<k or k==0:
        return [[]]
    for elm in lst:
        sub_lst=lst[:]
        sub_lst.remove(elm)
        choose_sets_help(sub_lst,k,ans)       
    return ans
        
def choose_sets(lst,k):
    return choose_sets_help(lst,k,[])

and it works perfectly but then my teacher said i cant check for any repetitions in my code so the line :"if lst not in ans..." isn't allowed,
and now i cant think of a way to get the correct final list with no repetitioons in it
any ideas ?
thanks

[TrustyTony]

The result should include sublists of length k which do not contain first element and lists of first element followed by all sublists from other elements of length k - 1, when length of argument is more than k.

[ni5958]

The result should include sublists of length k which do not contain first element and lists of first element followed by all sublists from other elements of length k - 1, when length of argument is more than k.

i've thought about what you said and i've thought about how to implement this but i've still haven't solved it .

how i've figured it, it should have looked like that:

def choose_sets_help(lst, k,ans):
    ''' Input: lst,
        Output: a list of all k-length sub-lists '''
    if len(lst)==k :
        return lst
    if  k==0:
        return [[]]
    if len(lst)<k :
        pass
    else:
        for i in range(1,len(lst)):
            sub_lst=lst[1:]
            if len(sub_lst)==k:
                ans.append(sub_lst)
                break
            else:
                sub_lst.remove(lst[i])
                ans.append(choose_sets_help(sub_lst,k,ans))
        for j in range(1,len(lst)):
            sub_lst2=lst[:]
            if len(sub_lst2)==k:
                ans.append(sub_lst2)
                break
            else:
                sub_lst2.remove(lst[j])
                ans.append(choose_sets_help(sub_lst2,k,ans)) 
    return ans
        
def choose_sets(lst,k):
    return choose_sets_help(lst,k,[])

where the first loop(i-index) always leaves the first element out, and the second loop (j-index), always leaves him in

by the way, i dont like using the 'break' method but i'm not sure how to do it differently

[Gribouillis]

The result should include sublists of length k which do not contain first element and lists of first element followed by all sublists from other elements of length k - 1, when length of argument is more than k.

I don't agree with Tony, I think it's better to find all the lists with k-1 elements in the n-1 first items, and for each of these lists, add all the possible last elements.

[ni5958]

i got it!

def choose_sets(lst, k):
    ''' Input: lst,
        Output: a list of all k-length sub-lists '''
    if len(lst)==k :
        return [lst]
    if  k==0:
        return [[]]
    if k==1:
        return [[i] for i in lst]
    sub_lst1=choose_sets(lst[1:],k-1)
    for i in sub_lst1:
        i.append(lst[0])
    sub_lst2=choose_sets(lst[1:],k)
    final_lst=[]
    final_lst.extend(sub_lst1)
    final_lst.extend(sub_lst2)
    return final_lst

i think it wouldn't have mattered if i would cut the first element or the last element
thanks for all the help!

[Gribouillis]

Your solution looks good, but it changes the order of the list items. Here is another solution which preserves order

def choose_range(n, k):
    if k == n:
        return [list(range(n))]
    elif k == 0:
        return [[]]
    elif k == 1:
        return [[i] for i in range(n)]
    result = []
    for lst in choose_range(n-1, k-1):
        result.extend(lst + [i] for i in range(lst[-1] + 1, n))
    return result
    
def choose_sets4(lst, k):
    return [ [lst[i] for i in ilist ] for ilist in choose_range(len(lst), k) ]

Here is another solution using generators

def gen_sublists(thelist, k):
    n = len(thelist)
    if k == 0:
        yield list(), 0
    elif k == n:
        yield list(thelist), n
    elif k < n:
        for sublist, idx in gen_sublists(thelist[:-1], k - 1):
            for i, item in enumerate(thelist[idx:], idx):
                yield sublist + [item], i + 1
                
def choose_sets1(thelist, k):
    if not 0 <= k <= len(thelist):
        raise ValueError((k, len(thelist)))
    return [ L for L, i in gen_sublists(thelist, k) ]

Here is a shorter solution using my generic tree traversal snippet http://www.daniweb.com/software-development/python/code/395270

from walktree import walk

def subnodes(node):
    L, S, idx, rest = node
    if rest > 0:
        for i in range(idx, len(L)):
            yield (L, S + [L[idx]], i + 1, rest - 1)

def choose_sets(lst, k):
    return [path[-1][1] for path in walk((lst,[], 0, 4), subnodes, walk.leaf, tree = True) if path[-1][-1] == 0]

Finally, it's worth reading the documentation of the standard module itertools for the best solution.

[TrustyTony]

Here is mine also for comparison:

def choose_sets(seq, k):
    if k == 0:
        return [[]]
    elif len(seq) == k:
        return [seq]
    else:
        with_first = [seq[0:1] + subs for subs in choose_sets(seq[1:], k - 1)]
        return with_first + choose_sets(seq[1:], k)

for t in ([1,2,3,4], 0), ([1,2,3,4], 2), ([1, 2, 3, 4], 4), (list('abcde'), 4):
    print t,':\n', choose_sets(*t)
    print

[ni5958]

both Gribouillis's first solution and pytony's solution looks good ..
its been about 6 days that i'm thinking about this problem, i was starting to think its not possible without checking for repetitions..
i think what helped me was the fact that to find how many k's you can choose from n you need to divied the problem to n-1,k + n-1,k-1

i'm not really familiar with generators, is it something worth spending time learning it?

[Gribouillis]

i'm not really familiar with generators, is it something worth spending time learning it?

Generators are very useful and powerful, furthermore, they are pythonic. Most builtin functions returning sequences have become generators. It's definitely worth spending time learning it. You can see some nice examples in David Beazley's papers http://www.dabeaz.com/generators/ . Every time a function needs to produce a sequence, try to write a generator.

There is an example generator implementation of your function in itertools.combinations()'s documentation http://docs.python.org/library/itertools.html?highlight=combinations#itertools.combinations. Its algorithm looks close to itertools C implementation http://svn.python.org/view/python/trunk/Modules/itertoolsmodule.c?revision=81889&view=markup .