2

To clarify the picture, if i have a string:

'pac'

I would want to get the list of every permutation of it, in this example:

['p', 'a', 'c', 'pa', 'pc', 'pac']

Just like i would type any of it in some search engine like the one on Ebay and it would pop up "pac" as a suggestion.

Code bellow is what i achieved thus far, but it's obviously not working as it should. 'Names' is just a list with multiple names, for instance: ['pac', 'greg', 'witch']

    letters = {}
    for name in names:
        temp = []
        letter = []
        temp2 = []

        for let in name:
            let = let.lower()
            temp.append(let)
            letter.append(let)

        for i in range(0, len(name)):
            for j in range(1, len(name) - i):
                print(i, j, end='  ')

                to_add = letter[i] + temp[j]
                print(to_add, temp2)

                temp2.append(to_add)
                letter.append(to_add)
            temp = temp2
            temp2 = []

        letters[name] = letter
    return letters

If there is built-in function feel free to share it with me, but that's not the core of the problem.

Artism
  • 53
  • 1
  • 7
  • Possible duplicate of https://stackoverflow.com/questions/8306654/finding-all-possible-permutations-of-a-given-string-in-python – dmitryro Jun 30 '18 at 03:11
  • 1
    Just use permutations and list comprehension - your code contains a lot of extra work. – dmitryro Jun 30 '18 at 03:11
  • Possible duplicate of [Finding all possible permutations of a given string in python](https://stackoverflow.com/questions/8306654/finding-all-possible-permutations-of-a-given-string-in-python) – Matthew Story Jun 30 '18 at 03:12
  • What happened to 'ac'? And it looks like you want combinations, not permutations. The set of all combinations is called the power set, see the itertools docs for a recipe. – PM 2Ring Jun 30 '18 at 03:27

1 Answers1

6

User standard library itertools:

In [48]: T = 'pac'

In [49]: list(itertools.chain(*[itertools.combinations(T, i+1) for i in range(len(T))]))
Out[49]: [('p',), ('a',), ('c',), ('p', 'a'), ('p', 'c'), ('a', 'c'), ('p', 'a', 'c')]

It break down into:

1, itertools.combinations(['p', 'a', 'c'], i) to generate all the subsample of 'pac' with sample size i

2, repeat i for i=1, 2, 3, and put the resultant three itertools.combination objects in a list

3, unpack the list from #2, and use the those as the parameter to generate an itertools.chain object (as the name implies, it will chain its args together). See more on arguments unpack

In a lot of real world use cases, especially when the total number of the elements are large, you don't actual want to make a list out of the itertools.chain object. The point of using itertools are often to achieve memory efficiency by avoiding having to putting all its members in memory.

(if you don't want tuples just add a ''.join to get them back to strings)

CT Zhu
  • 52,648
  • 17
  • 120
  • 133
  • 1
    I understand what is going on here, but I think you should *generally* explain what is going on with the line: `list(itertools.chain(*[itertools.combinations(list(T), i+1) for i in range(len(T))]))` so that way OP doesnt just copy+paste, but learns HOW it works. – Fallenreaper Jun 30 '18 at 03:16
  • 1
    You really don't need `list(T)` and your claim for memory efficiency is lost (for this example - but generally true) because you expand the arguments to `itertools.chain()`. You could maintain memory efficiency with `itertools.chain.from_iterable(itertools.combination(T, i+1) for i in range(len(T)))` - a generator expression vs an expanded list comprehension. – AChampion Jun 30 '18 at 03:32