Generating all the permutations of two digits of equal number

Question

Here I am given two numbers 1 and 0 of equal quantity. Now I am trying to Find the possible permutaions of it. like this suppose I have give 2 1's and 2 0's. I start form this 0011. than I move the first 1 along left generating 0101 and then 1001. now I move the second 1 generating 1010 and 1100. Will this approach work. I am short of 0110 and I cant figure How to do this. I suppose there is way like recursive backtracking to do this. But I don't know the technique backtracking. i do Understand recursion though. So Can anyone tell me the approach please?? either iterative or recursive.If possible both. I am trying to find all possible permutaions. for 2 1's and 0's , it is 1001,1100,1010,0101,0110,0011. that is here 4!/(2!*2!) permutations. How do I do it for more, like 111000 or 11110000 ? and the language would be C++. and for clarification it can be any chars, like ooii or kkjj. that should be string I am manipulating

Answer 1

Do some reading into sorting algorithms in the language you prefer. Here goes some descriptions of types of sorting:

https://en.wikipedia.org/wiki/Sorting_algorithm

OR

I have no idea what you are talking about.

Answer 2

This sounds like a homework question (correct me if I'm wrong), so I'm just going to provide some pseudo-code to illustrate the general approach. You'll have to figure out how to adapt the algorithm to work in C++ (and hopefully understand it in the process).

The idea is to take each character and append it to each permutation of the remaining characters, recursively. The base case is the empty string.

function foo (List<char> chars)
    List<string> permutations = new List<string>()
    for i:0..chars.length - 1
        List<string> subPermutations = foo(chars.removeAt(i))
        for each string perm in subPermutations
            permutations.add(chars.get(i) + perm)
        end for
    end for
    if permutations is empty
        permutations.add("")
    end if
    return permutations
end foo

As an added note, as you're specifically dealing with 2 different characters repeated, this will give you a lot of duplicate permutations. Your options are to check whether a permutation has already been generated before adding it to the list, remove duplicates from the list at the end, or optimize the recursion for your situation.