How to get all substrings & all character permutations of all substings?

Question

I have a string f.e. str = 'abc'

I want to get all combinations like this:

'a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca','cb', 'abc', 'acb', 'bca' , 'bac', 'cab', 'cba'

I tried

def string_set(str):
    n = len(str) 
    arr = [] 

    for i in range(0,n):  
        for j in range(i,n): 
            arr.append(str[i:(j+1)])

    return arr

but it olny gave me:

'a', 'ab', 'abc', 'b', 'bc', 'c'.

How can I include the rest ones?

Since you are doing `str[i:(j+1)]` you are only getting the "contiguous" substrings. Also, `str` is a very bad choice for a variable name — DeepSpace, Sep 19 '20 at 19:56
@DeepSpace Substrings are contiguous by definition. They just want more than substrings. — superb rain, Sep 19 '20 at 20:01
The question which is supposedly answers this question does not answer it. It does not deal with permutations, the OP here wants all permutations as well. — zabop, Sep 19 '20 at 20:02
@zabop True, but my point rather was that you might want to try that, as your solution is very complicated. — superb rain, Sep 19 '20 at 20:08

zabop · Accepted Answer · 2020-09-19T20:34:21.397

1

import itertools

You can do, using itertools permutations & combinations:

def string_set(x):
    arr = [''.join(l) for i in range(len(x)) for l in itertools.combinations(x, i+1)]     
    reslist=[]   
    for eachpermut in arr:
        for each in [''.join(eachpermut) for eachpermut in list(itertools.permutations(eachpermut))]:
            reslist.append(each)
    return reslist

If you like everything in one line:

def string_set(x):
    return [each for eachpermut in [''.join(l) for i in range(len(x)) for l in itertools.combinations(x, i+1)] for each in [''.join(eachpermut) for eachpermut in list(itertools.permutations(eachpermut))]]

string_set('abc') returns:

['a',
 'b',
 'c',
 'ab',
 'ba',
 'ac',
 'ca',
 'bc',
 'cb',
 'abc',
 'acb',
 'bac',
 'bca',
 'cab',
 'cba']

If you don't want to import itertools, you can just use their permutations functions only:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Then just do permutations instead of itertools.permutations in the above code.

Can do the same with combinations.

edited Sep 19 '20 at 20:34

answered Sep 19 '20 at 19:59

zabop

6,750
3
39
84

I liked this:) btw. How can I do this without itertools library? – kishmish17 Sep 19 '20 at 20:08
there are no 'ac', 'ca' (( – kishmish17 Sep 19 '20 at 20:13
oh ok, looking into it... – zabop Sep 19 '20 at 20:14
@kishmish17 Your title says "all substrings & all of their permutations" and that's what this code does (except for the empty substring). 'ac' and 'ca' are not a permutation of a substring. – superb rain Sep 19 '20 at 20:17
check it now, I think it works – zabop Sep 19 '20 at 20:18
@superbrain, why not? it is a permutation of a and c. – zabop Sep 19 '20 at 20:19
You could use **powerset** from [itertools recipes](https://docs.python.org/3/library/itertools.html#itertools-recipes) with a change to use **permutations** instead of **combinations**. – Chris Charley Sep 19 '20 at 20:20
@zabop If you argue like that, then you should also say that abbc should be there, as it's a permutation of ab and bc (I don't think so, but apparently you do). – superb rain Sep 19 '20 at 20:22
Yes that is correct - maybe can you suggest a better title? (I edited that title to its current state). – zabop Sep 19 '20 at 20:23
@blhsing I tried it and was going to post before the post was closed. It permutes all combinations of the powerset. I thought that was what the OP wanted. – Chris Charley Sep 19 '20 at 20:24
@ChrisCharley Yes, switching combinations to permutations in the powerset recipe would be the correct approach. I've re-opened the question since it isn't exactly a duplicate. – blhsing Sep 19 '20 at 20:28
Edited the question, is it better now? – zabop Sep 19 '20 at 20:29
Yeah, powerset would be great. – zabop Sep 19 '20 at 20:29
I was wrong about the output in this answer, now edited it. Now if I do: `set(string_set('abc')) - set(['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca','cb', 'abc', 'acb', 'bca' , 'bac', 'cab', 'cba'])`, it gives me an empty set, `set(['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca','cb', 'abc', 'acb', 'bca' , 'bac', 'cab', 'cba']) - set(string_set('abc'))` also. (The long list is the OP's desired output.) Are you sure I am wrong? (I am not certain I am right.) – zabop Sep 19 '20 at 20:37

How to get all substrings & all character permutations of all substings?

1 Answers1