python get all subset by recursive function

user_4319593 0
Viewed 297

I made some python code to get all subset by recursive.

if given a data

data = [1,2,3,4,5]
length = 3

the result will print all subset at 3 length like this

1,2,3
1,2,4
1,2,5
2,3,4
2,3,5...

this is my code

data = [1,2,3,4,5]
n = 5
r = 3 
    templist = []
    def re(max,length,idx):
        if idx == max:
            return
        if idx == length:
            for i in templist:
                print(" "+str(i))
            print("\n")
            return
        else:
            templist.append(data[idx])
            re(max,length,idx+1)
            templist.pop()
            re(max,length,idx+1)
    if __name__ == "__main__":
     re(n,r,0)

my expectaion it loop all the possible subset but it will fail when it encouter call re(max,length,idx+1) after temlist.pop()

when code enter the second re() function I expected it append templist.append(data[4]) because first re() function return by if condition if idx == length:

when idx is 3, idx is the same the length(3). so the recursive end,run temlist.pop() and it will enter the second re(4) function because I coded idx+1

but it will fail idx only be circled between 2~3

so I changed second recursive function

re(max,length,idx+1)

to

re(max,length,idx+2)

and I totally broken.

I think the logic I made was bascally wrong. but I don't know where to fix it how can I solve to call recursive as I expected?

subset tail-recursion recursion algorithm python
2 Answers

Here is how:

def func(data, length, lst=[]):
    for i in data[length - 1:]:
        lst.append(data[:length - 1] + [i])
    if data:
        func(data[1:], length, lst)
    return lst

data = [1,2,3,4,5]
length = 3

print(func(data, length))

Output:

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

Explanation:

  1. Define a function that takes in three parameters, the list (data), the length (length) and an empty list (lst) to store the output values (defining it outside the function is considered bad practice).

  2. Iterate through the elements of the data list besides the first length - 1 indexed elements, and append the elements from the 0 index to the length - 1 index plus the current element of the iteration.

  3. If the data list didn't go empty, call the current function again, but using the slice [1:] to remove the first character.

  4. If the data list didn go empty, return the lst list.

Your other option is to use Python's powerful generators. Using this technique, we no longer need the lst parameter -

def func(data, length):
    for i in data[length - 1:]:
        yield data[:length - 1] + [i]
    if data:
        yield from func(data[1:], length)

Now we can retrieve the permutations using iteration -

data = [1,2,3,4,5]
length = 3

for perm in func(data, length):
  print(perm)

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

Or we can gather all permutations in a list -

data = [1,2,3,4,5]
length = 3

print(list(func(data, length)))

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]
user_135524700

The best method to do this is by using the builtin permutations from itertools.

from itertools import permutations
data = [1,2,3,4,5]
length = 3
res = list(permutations(data, length))
user_139750770
Related