CODEWITHSUNDEEP
pythonpython-3.xalgorithm
Artism
Artism

Reputation: 53

Combinations without duplicates of all elements in Python

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.

Upvotes: 2

Views: 3352

Answers (1)

CT Zhu
CT Zhu

Reputation: 54340

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)

Upvotes: 6

Related Questions