CODEWITHSUNDEEP
stringalgorithmrecursionpermutation
user130075
user130075

Reputation: 25

Generate string permutations recursively; each character appears n times

I'm trying to write an algorithm that will generate all strings of length nm, with exactly n of each number 1, 2, ... m,

For instance all strings of length 6, with exactly two 1's, two 2's and two 3's e.g. 112233, 121233,

I managed to do this with just 1's and 2's using a recursive method, but can't seem to get something that works when I introduce 3's.

When m = 2, the algorithm I have is: 

generateAllStrings(int len, int K, String str) 
{
    if(len == 0) 
    {
        output(str);
    }

   if(K > 0) 
   {
       generateAllStrings(len - 1, K - 1, str + '2'); 
    }      
   if(len > K)  
   {
        generateAllStrings(len - 1, K, str + '1'); 
    }
}

I've tried inserting similar conditions for the third number but the algorithm doesn't give a correct output. After that I wouldn't even know how to generalise for 4 numbers and above.

Is recursion the right thing to do? Any help would be appreciated.

Upvotes: 1

Views: 215

Answers (3)

m69 ''snarky and unwelcoming''
m69 ''snarky and unwelcoming''

Reputation: 12324

To use a simple recursive algorithm, give each recursion the permutation so far (variable perm), and the number of occurances of each digit that is still available (array count).
Run the code snippet to generate all unique permutations for n=2 and m=4 (set: 11223344).

function permutations(n, m) {
    var perm = "", count = [];                   // start with empty permutation
    for (var i = 0; i < m; i++) count[i] = n;    // set available number for each digit = n
    permute(perm, count);                        // start recursion with "" and [n,n,n...]

    function permute(perm, count) {
        var done = true;
        for (var i = 0; i < count.length; i++) { // iterate over all digits
            if (count[i] > 0) {                  // more instances of digit i available
                var c = count.slice();           // create hard copy of count array
                --c[i];                          // decrement count of digit i
                permute(perm + (i + 1), c);      // add digit to permutation and recurse
                done = false;                    // digits left over: not the last step
            }
        }
        if (done) document.write(perm + "<BR>"); // no digits left: complete permutation
    }
}

permutations(2, 4);

Upvotes: 0

user4668606
user4668606

Reputation:

You can easily do this using DFS (or BFS alternatively). We can define an graph such that each node contains one string and a node is connected to any node that holds a string with a pair of int swaped in comparison to the original string. This graph is connected, thus we can easily generate a set of all nodes; which will contain all strings that are searched:

set generated_strings
list nodes

nodes.add(generateInitialString(N , M))
generated_strings.add(generateInitialString(N , M))

while(!nodes.empty())
    string tmp = nodes.remove(0)

    for (int i in [0 , N * M))
        for (int j in distinct([0 , N * M) , i))
            string new = swap(tmp , i , j)
            if (!generated_strings.contains(new))
                nodes.add(new)
                generated_strings.add(new)

//generated_strings now contains all strings that can possibly be generated.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372724

One option would be to list off all distinct permutations of the string 111...1222...2...nnn....n. There are nice algorithms for enumerating all distinct permutations of a string in time proportional to the length of the string, and they'd probably be a good way to go about solving this problem.

Upvotes: 1

Related Questions