Find all combinations of values between two arrays where values from one may only be used once?

Question

I have two very simple arrays, one containing characters, and the other containing numbers. Without repeating any values from the numbers array, I need to find all possible combinations of the array values. Given the following two data sets:

char[] characters = { 'a', 'b' };
int[] numbers = { 1, 2, 3 };

The expected output is:

1a2a3
1a2b3
1b2a3
1b2b3

If a number is repeated, it should be counted a second time. For example, if we change the numbers data set to 1, 2, 2 the expected output is:

1a2a2
1a2b2
1b2a2
1b2b2

I've looked at many examples that demonstrate using recursion (and in some cases Linq was used), to find all possible combinations of the values in one array, and even a few samples of across two, but in all of the samples I've seen, the resulting data set was a 1 to 1 mapping such as a1, b1, a2, b2, a3, b3, which is not what I need.

I've tried few different approaches, but none have worked, nor were they scalable so there's no need to post those here as I abandoned them all along the way. Think along the lines of:

foreach (char character in characters) {
    foreach (int number in numbers) {
        for (int i = characters.Length - 1; i > 0; i--) {
            // Not scalable, probably why recursion is used as a solution.
        }
    }
}

I'm having trouble getting my brain to move this to recursion for some reason.

---

How do I create all possible combinations of the values in two arrays, where the length of both arrays are unknown, and the values in one array are not repeated (unless specified in the dataset itself)?

NOTE: The results should be stored in a List<string> for later processing.

Answer 1

The CountWithUniqueChars class below is simply a pared down version of my Revision class here.

Code:

class Program
{
    static void Main(string[] args)
    {
        string characters = "ab";
        int[] numbers = { 1, 2, 3 };

        int sequenceLength = numbers.Length - 1;
        string startingSequence = new string(characters[0], sequenceLength);
        CountWithUniqueChars sequence = new CountWithUniqueChars(characters, startingSequence);

        StringBuilder sb = new StringBuilder();
        List<string> sequences = new List<string>();
        do
        {
            sb.Clear();
            for(int i=0; i<numbers.Length; i++)
            {
                sb.Append(numbers[i]);
                if (i < (numbers.Length - 1)) {
                    sb.Append(sequence.CurrentSequence[i]);
                }
            }
            sequences.Add(sb.ToString());
            sequence.NextSequence();
        } while (sequence.CurrentSequence.Length == sequenceLength);

        foreach (String curSequence in sequences)
        {
            Console.WriteLine(curSequence);
        }

        Console.Write("Press Enter to Quit...");
        Console.ReadLine();
    }

}

public class CountWithUniqueChars
{

    private string chars;
    private char[] values;

    private System.Text.StringBuilder curSequence;

    public CountWithUniqueChars()
    {
        this.DefaultSequnce();
    }

    public CountWithUniqueChars(string validChars)
    {
        if (validChars.Length > 0)
        {
            chars = validChars;
            values = validChars.ToCharArray();
            curSequence = new System.Text.StringBuilder(values[0]);
        }
        else
        {
            this.DefaultSequnce();
        }
    }

    public CountWithUniqueChars(string validChars, string startingSequence)
        : this(validChars)
    {
        curSequence = new System.Text.StringBuilder(startingSequence);
        int i = 0;
        for (i = 0; i <= curSequence.Length - 1; i++)
        {
            if (Array.IndexOf(values, curSequence[i]) == -1)
            {
                curSequence = new System.Text.StringBuilder(values[0]);
                break;
            }
        }
    }

    private void DefaultSequnce()
    {
        chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        values = chars.ToCharArray();
        curSequence = new System.Text.StringBuilder(values[0]);
    }

    public string ValidChars
    {
        get { return chars; }
    }

    public string CurrentSequence
    {
        get { return curSequence.ToString(); }
    }

    public string NextSequence()
    {
        this.Increment();
        return this.CurrentSequence;
    }

    private void Increment()
    {
        char curChar = curSequence[curSequence.Length - 1];
        int index = Array.IndexOf(values, curChar);
        if (index < (chars.Length - 1))
        {
            index = index + 1;
            curSequence[curSequence.Length - 1] = values[index];
        }
        else
        {
            curSequence[curSequence.Length - 1] = values[0];
            int i = 0;
            int startPosition = curSequence.Length - 2;
            for (i = startPosition; i >= 0; i += -1)
            {
                curChar = curSequence[i];
                index = Array.IndexOf(values, curChar);
                if (index < (values.Length - 1))
                {
                    index = index + 1;
                    curSequence[i] = values[index];
                    return;
                }
                else
                {
                    curSequence[i] = values[0];
                }
            }
            curSequence.Insert(0, values[0]);
        }
    }

}

Output:

1a2a3
1a2b3
1b2a3
1b2b3
Press Enter to Quit...

Another example using different inputs:

string characters = "abc";
int[] numbers = { 1, 2, 3, 4};

Output:

1a2a3a4
1a2a3b4
1a2a3c4
1a2b3a4
1a2b3b4
1a2b3c4
1a2c3a4
1a2c3b4
1a2c3c4
1b2a3a4
1b2a3b4
1b2a3c4
1b2b3a4
1b2b3b4
1b2b3c4
1b2c3a4
1b2c3b4
1b2c3c4
1c2a3a4
1c2a3b4
1c2a3c4
1c2b3a4
1c2b3b4
1c2b3c4
1c2c3a4
1c2c3b4
1c2c3c4
Press Enter to Quit...