How to efficiently generate combination without repetition with certain distinctive number between them

Question

How to efficiently generate sets of number combination without repetition where all sets has certain distinctive number between each other.
*NOTE : Range number will always start from 0.

---

Example :

Range Number (numbers[ ]) = 0,1,2,3,4,5,6,7 ==> total 8 numbers (n).
Combination (k) = 5 numbers.
Distinctive numbers (nD) = 2 numbers.

Results :
0 1 2 3 4
0 1 2 5 6
0 1 3 5 7
0 1 4 6 7
0 2 3 6 7
0 2 4 5 7
0 3 4 5 6
There are 7 valid combinations

---

How it Assembled :

Since i'm not good with words, so let me visualized them as like this :

To explain about their distinctive numbers :

And we could summarize them into this table :

---

What have i achieved so far

My current solution is very inefficient (or you can call it brute force).
* First i loop for each combination. ==> k C n
* Then i create a temp for valid combination.
* Then for each combination i validate towards my temp, if its valid then store it in temp, otherwise ignore it.
Thats it.

Here is my code in Console App :

class Program
{
    static List<int[]> ValidCombinations;

    static void Main()
    {
        ValidCombinations = new List<int[]>();

        int[] numbers = Enumerable.Range(0, 8).ToArray();
        int n = numbers.Length;
        const int k = 5;
        const int nD = 2;

        int maxIntersect = k - nD;

        int iCombination = 0;
        int iValidCombination = 0;
        int[] _temp = new int[k];
        foreach (int[] c in FindCombinations(k, n))
        {
            // #Print out
            for (int i = 0; i < n; i++)
            {
                if (c.Contains(i))
                    Console.Write(c[Array.IndexOf(c, i)] + " ");
                else
                    Console.Write("_ ");
            }

            // Save to List
            if (IsValidSet(c, maxIntersect))
            {
                _temp = new int[k];
                for (int i = 0; i < c.Length; i++)
                {
                    _temp[i] = c[i];
                }
                ValidCombinations.Add(_temp);
                iValidCombination++;
                Console.Write(" ### --> {0}", string.Join(" ", c));
            }
            Console.WriteLine();

            iCombination++;
        }
        Console.WriteLine("\nTotal Combination = {0}", iCombination);
        Console.WriteLine("Valid Combination Found = {0}", iValidCombination);
    }

    public static IEnumerable<int[]> FindCombosRec(int[] buffer, int done, int begin, int end)
    {
        for (int i = begin; i < end; i++)
        {
            buffer[done] = i;

            if (done == buffer.Length - 1)
                yield return buffer;
            else
                foreach (int[] child in FindCombosRec(buffer, done + 1, i + 1, end))
                    yield return child;
        }
    }

    public static IEnumerable<int[]> FindCombinations(int m, int n)
    {
        return FindCombosRec(new int[m], 0, 0, n);
    }

    private static bool IsValidSet(int[] set, int maxIntersect)
    {
        foreach (var item in ValidCombinations)
        {
            if (set.Intersect(item).Count() > maxIntersect)
                return false;
        }

        return true;
    }
}

I got the base code to generate the combination from here.

---

The Issues

This is work, but for greater range of numbers, this solution will takes a lot of time to complete. I know because the combination algorithm involved , but there must be some kind of shortcut or pattern to simplified it (which my tiny brain has failed to figure it out).

Thank you very much.

Answer 1

Your matrix representation shows that this problem is homologous or at least very similar to finding a set of different binary words of fixed size, constant Hamming weight and with a constant Hamming distance between any pair of them.

Graphically:

As described in this question, this problem is not necessarily trivial. In particular, the proposed solution explains how to construct the Hadamard matrix, which rows are the binary words you are looking for.

This looks very similar to your matrix. Anyway, what you need is a little bit more general. Unlike that case, you don't want every pair of rows to have exactly a distance of n/2, but a constant distance of d < n/2.

Bottom line

The possibility to easily generate sets of binary words with constant size (determined by your numbers array's length), constant weight (determined by your k) and constant distance (determined by your nD) depends heavily on these parameters. Given that some techniques for generating those sets rely on some assumptions over these parameters, my guess is that there is no efficient algorithm for the general case.

Anyway, it might be useful if you reword your question and ask it on MathOverflow, maybe linking both this question and the one I linked.

Algorithm suggestion

As for an algorithm (that, just as yours, won't work with big numbers), you could try the following:

1. Generate a binary word made up of k ones followed by (numbers.Length - nD) zeroes and store it in a list
2. Iteratively generate every word which has exactly 2*nD bits different to your original word.
3. For each generated word, try to store it in the list only if it has 2*nD distance to each other word in the list.

Not so different from your approach, but I think that could work a little bit better, thou.