Find valid assignments of integers in arrays (permutations with given order)

Question

I am having a general problem finding a good algorithm for generating each possible assignment for some integers in different arrays.

Lets say I have n arrays and m numbers (I can have more arrays than numbers, more numbers than arrays or as much arrays as numbers).

As an example I have the numbers 1,2,3 and three arrays:

{ }, { }, { }

Now I would like to find each of these solutions:

{1,2,3}, { }, { }
{ }, {1,2,3}, { }
{ }, { }, {1,2,3}
{1,2}, {3}, { }
{1,2}, { }, {3}
{ }, {1,2}, {3}
{1}, {2,3}, { }
{1}, { }, {2,3}
{ }, {1}, {2,3}
{1}, {2}, {3}

So basically I would like to find each possible combination to assign the numbers to the different arrays with keeping the order. So as in the example the 1 always needs to come before the others and so on...

I want to write an algorithm in C++/Qt to find all these valid combinations.

Does anybody have an approach for me on how to handle this problem? How would I generate these permutations?

ADDITIONS

Unfortunately I didn't manage to change the great examples you gave for the problem I have now, since the numbers that I want to arrange in the arrays are stored in an array (or for me a QVector)

Can anybody help me change the algorithm so that it gives me each possible valid combination of the numbers in the QVector to the QVector< QVector > so that I can do further computations on each one?

QVector<int> line; // contains the numbers: like {7,3,6,2,1}
QVector< QVector<int> > buckets; // empty buckets for the numbers { {}, {}, {} }

QList< QVector< QVector<int> > > result; // List of all possible results

Would be really great if anyone could provide me with a simple implementation that works or tips on how to get it... I just couldn't change the code that was already provided so that it works...

Answer 1

This will be easy with backtracking recursion. You should track which array you are filling and which number you are up to. Something like that:

void gen(int arrayN, int number)
{
   if (number == MAX_NUMBER + 1) //We have a solution
   {
        printSolution();
        return;
   }

   if (arrayN == MAX_ARRAYS + 1) //No solution
       return;

   gen(arrayN + 1, number); //Skip to next array

   for (int i = number; i <= MAX_NUMBER; i++)
   {
       //Save at this line the numbers into an array for the solution
       gen(arrayN + 1, i + 1); //Used the numbers from "number" to "i" inclusive
   }
}

gen(0, 1);