Monday, March 28, 2011

Need recursive function for generating unique combination of strings

I have some(say 9, no not definite) unique strings from database(A,B,C,D,E,F,G,H) and I want to create unique combination of these fields to populate the listbox so that user can select single or different combination of these string fields like A,B,C,D,E,F,G,H, AB,AC,AD,AE,AF,AG,AH,AC,AD,AE,AF,AG,AG,AH,... ABC,ABD,ABE,ABF,ABG,ABH,ACD,ACE,ACF,ACG,ACH,.....

In C# (win application) Thanks in advance

From stackoverflow
  • This is like counting integers in base 'n' .. should not be difficult.

    : But I need Unique combination and not double(AA,BB) or repeated combinations(AB,BA)
  • My first choice would be "use a CheckedListBox and let the user make their picks themselves" - this will save their sanity... would you want to look for "ABCEFH" in a long list?).

    If you want the strings: How about just using binary arithmetic? i.e. use a number (bit-length as per the number of elements), and simply keep incrementing, including the set bits each time? So in C#, for example:

    static void Main()
    {
        foreach (string value in GetCombinations(
            "A", "B", "C", "D", "E", "F", "G", "H"))
        {
            Console.WriteLine(value);
        }
    }
    static IEnumerable<string> GetCombinations(params string[] tokens)
    {
        ulong max = (ulong) 1 << tokens.Length;
        StringBuilder builder = new StringBuilder();
        // test all bitwise combinations
        for (ulong value = 0; value < max; value++)
        {
            builder.Length = 0;
            ulong tmp = value;
            // include the tokens for the set bits
            for (int i = 0; i < tokens.Length; i++)
            {
                if ((tmp & (ulong)1) == 1) builder.Append(tokens[i]);
                tmp >>= 1;
            }
            yield return builder.ToString();
        }
    }
    

    If you want the data in the order per your example, LINQ is helpful:

        foreach (string value in GetCombinations(
              "A", "B", "C", "D", "E", "F", "G", "H")
            .OrderBy(s=>s.Length)
            .ThenBy(s=>s))
        {
            Console.WriteLine(value);
        }
    

0 comments:

Post a Comment