Python Forum

i am looking for code (preferably a function) that when given a sequence, such as a string of letters, will create a list or set (of strings or tuples) or tuple of all possible combinations of the elements of the given sequence, in the order present in that given sequence. the order of the resulting combinations is not important, hence a set is valid for the results. for example:

given string:
"skap"

a valid result:
["s","sk","ska","skap","sap","sa","sp","skp","k","ka","kap","ap","a","p","kp"]

other orders of the same set of strings would be valid.  any sequence or set with any of these (not a complete list) would be an invalid result:
"ss", "spk", "paks"

given list:
[ 3, 1, 4]

a valid result:
[[3], [3,1], [3,1,4], [3,4], [1], [1,4], [4]]

again, the order does not matter, so this is also a valid result:
[[4], [1,4], [3,4], [1], [3,1,4], [3], [3,1]]

there should not be duplicates, so this should be considered to be an invalid result:
[[4], [1,4], [1], [3,4], [1], [3,1,4], [3], [3,1]]

you would not have this issue with sets:
{(3,),(3,1),(3,1,4),(3,4),(1,)(1,3),(4,)}

i don't know the mathematical terminology for this.  i think it would be part of set theory.

First try:

#!/usr/bin/python3
import itertools

def algo(liste):
    result = [ liste ]
    for i in range(1, len(liste)):
        result.extend(list(itertools.combinations(liste, i)))
    return result

result = algo([1,2,3,4])
print(len(result), result)
#done

Output:
15 [[1, 2, 3, 4], (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

that looks good.  Danke!

Bitte.
https://en.wikipedia.org/wiki/Permutation
https://en.wikipedia.org/wiki/Combination

If you stumble across an easy algorithmn without itertools,
let me know. Thanks.

(Nov-18-2017, 05:04 AM)heiner55 Wrote: [ -> ]If you stumble across an easy algorithmn without itertools,
let me know. Thanks.

i have not tested this idea, yet.  for a given sequence of n items, iterate over range(1,2**n) as b..  get a string of bits representing b and start an empty list.  iterate through this string of bits.  for each bit that is 1 get the corresponding element from the given sequence at the same position and append it to the list.  when the iteration of bits is done, yield the resulting list (or append it to the big list to be returned).

yes, i am thinking this should be a generator or a stack of generators.

Good idea.