How to get the permutations without repetition of all the combinations of a set of letters?

Question

I'm trying to create an algorithm that after giving it a number of random letters, for example: abcd, it shows you all the possible permutations, in this case, the answer would be:

abcd abc abd acd ab ac ad a bcd bc bd b cd c d

As you can see, the different permutations must have different letters, I have spent hours trying to do it without success, this is what I did so far:

        vector<char> letters;

        letters.push_back('a');
        letters.push_back('b');
        letters.push_back('c');
        letters.push_back('d');

        int number_of_letters = 4;
        int number_of_repetitions;
        vector<char> combination;
        vector<char> comb_copy;

        for(int i = 0; i < number_of_letters; i++){
            number_of_repetitions = 1;
            changing_letters = number_of_letters - (i + 1);

            for(int j = i+1; j < number_of_letters; j++){
                combination.push_back(letters[j]);
            }


            comb_copy = combination;

            for(int i = 0; i < comb_copy.size(); i++){
                cout << comb_copy[i];
            }

            while(number_of_repetitions <= changing_letters){
                comb_copy = combinations(comb_copy, number_of_repetitions);

                for(int i = 0; i < comb_copy.size(); i++){
                    cout << comb_copy[i];
                }

                comb_copy = combination;
                number_of_repetitions++;
            }
        }




vector<char> combinations(vector<char> combi, int reps){

    combi.erase(combi.end() - reps);

    return (reps > 1?combinations(combi, reps-1):combi);
}

And this is what I'm getting:

abcd abc abd acd bc bd c

I would need to get:

abcd abc abd acd ab ac ad a bcd bc bd b cd c d

Can someone help me? :)

Thanks!!

Please explain the results you are getting compared to what you expect. — codeMagic, Dec 30 '19 at 17:20
You are doing more than just permutation! You are creating subsets then taking the permutation of each subset. Perhaps if you did two separate methods then combined them you would get the result you seek. Also, where are your test cases? — Guy Coder, Dec 30 '19 at 17:31
@codeMagic I have updated it with the results I'm getting, and the results I need — feglex, Dec 30 '19 at 17:46
@NicoSchertler it is pretty helpful, the only thing is that in that post, they are getting all the combinations of k elements from n, and I need it to give me all the combinations of k elements from k to 1 element — feglex, Dec 30 '19 at 17:55
So just use any of this method using `k` from `1` to `n`. Better yet, many of these methods work recursively, i.e., they first compute all 1-combinations, then from these all 2-combinations and so on. So you already have all you need. — Nico Schertler, Dec 30 '19 at 19:28

MBo · Accepted Answer · 2019-12-30T19:50:48.353

You want to get all subsets of n items except for empty one. There are 2^n-1 such subsets. A pair of methods to generate them:

1) Make loop for value R in range 1..2^n-1. At every step represent R in binary. Every non-zero bit of R corresponds to index of initial array used in result. For example R=5=0101b denotes "ac" (0-th and 2-nd elements)

2) Use recursive procedure, at every level make two recursive calls - adding elelent with current index and omitting it. At the deepest level output result (if not empty)

Python examples:

s = "abcd"
n = len(s)
for r in range(1, 1<<n):
    result = ""
    for i in range(n):
        if r & (1 << i):
            result += s[i]
    print(result, end = " ")

a b ab c ac bc abc d ad bd abd cd acd bcd abcd 

def subs(s, result, idx):
    if idx == len(s):
        if len(result) > 0:
            print(result, end = " ")
    else:
        subs(s, result + s[idx], idx + 1)
        subs(s, result, idx + 1)

subs("abcd", "", 0)

abcd abc abd ab acd ac ad a bcd bc bd b cd c d

How to get the permutations without repetition of all the combinations of a set of letters?

1 Answers1