Algorithm to print all permutations with repetition of numbers

Question

I have successfully designed the algorithm to print all the permutations with the repetition of numbers. But the algorithm which I have designed has a flaw. It works only if the chars of the string are unique.

Can someone help me out in extending the algorithm for the case where chars of the string may not be unique.. My code so far :

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<iostream>

using namespace std;

void _perm(char *arr, char*result, int index)
{
    static int count = 1;
    if (index == strlen(arr))
    {
        cout << count++ << ". " << result << endl;
        return;
    }
    for (int i = 0; i < strlen(arr); i++)
    {
        result[index] = arr[i];
        _perm(arr, result, index + 1);
    }
}

int compare(const void *a, const void *b)
{
    return (*(char*)a - *(char*)b);
}



void perm(char *arr)
{
    int n = strlen(arr);
    if (n == 0)
        return;
    qsort(arr, n, sizeof(char), compare);
    char *data = new char[n];
    _perm(arr, data, 0);
    free(data);
    return;
}



int main()
{
    char arr[] = "BACD";
    perm(arr);
    return 0;
}

I am printing the output strings in lexicographically sorted way.

I am referring to the example.3 from this page.

http://www.vitutor.com/statistics/combinatorics/permutations_repetition.html

Thanks.

hi @stark92 ...check the following approaach..http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ — Karunakar, Nov 03 '14 at 12:40
@Karunakarn Correct me if I am wrong..Even that code works only if the string contains unique chars..It will print duplicates if the string does not contain unique chars. — starkk92, Nov 03 '14 at 13:18
Your code doesn't print permutations (of which there should be 4! == 24 for "ABCD"), but the result of four draws from the pool "ABCD" where each letter may be used more than once. — M Oehm, Nov 03 '14 at 13:48
c++ standard provides [`std::next_permutation`](https://en.cppreference.com/w/cpp/algorithm/next_permutation) (with possible implementation). — Jarod42, May 10 '21 at 08:10

score 2 · Answer 1 · edited Nov 03 '14 at 16:19

Your code doesn't print permutations, but four draws from the string pool with repetition. It will produce 4^4 == 256 combinations, one of which is "AAAA".

The code Karnuakar linked to will give you permutations of a string, but without distinguishing between the multiple occurrences of certain letters. You need some means to prevent recursing with the same letter in each recursion step. In C++, this can be done with a set.

The example code below uses a typical C string, but uses the terminating '\0' to detect the end. The C-string functions from <cstring> are not needed. The output will not be sorted unless the original string was sorted.

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

void perm(char *str, int index = 0)
{
    std::set<char> used;

    char *p = str + index;
    char *q = p;

    if (*p == '\0') {
        std::cout << str << std::endl;
        return;
    }

    while (*q) {
        if (used.find(*q) == used.end()) {
            std::swap(*p, *q);
            perm(str, index + 1);
            std::swap(*p, *q);

            used.insert(*q);
        }
        q++;
    }
}

int main()
{
    char arr[] = "AAABB";
    perm(arr);

    return 0;
}

This will produce 5! == 120 permutations for "ABCDE", but only 5! / (2! 3!) == 10 unique permutations for "AAABB". It will also create the 1260 permutations from the linked exercise.

Algorithm to print all permutations with repetition of numbers

1 Answers1

Linked