Python Forum
looking for code: combinations of letter in order
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
looking for code: combinations of letter in order
#1
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.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#2
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)]
Reply
#3
that looks good.  Danke!
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#4
Bitte.
https://en.wikipedia.org/wiki/Permutation
https://en.wikipedia.org/wiki/Combination
Reply
#5
If you stumble across an easy algorithmn without itertools,
let me know. Thanks.
Reply
#6
(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.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#7
Good idea.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020