I have a combinatorics problem that I am sure the smart people on xkcd can solve.

Take a normal combinatorics problem, but I want to find unique combinations can exist which have at least n differences from every other such combination.

If that makes sense?

## Combinatorics with minimum "distance"

**Moderators:** gmalivuk, Moderators General, Prelates

- Eebster the Great
**Posts:**2925**Joined:**Mon Nov 10, 2008 12:58 am UTC

### Re: Combinatorics with minimum "distance"

So for instance, each tuple of (0,0,0,0), (0,0,1,1), (1,1,0,0), (1,0,1,0), (0,1,0,1), (0,1,1,0), (1,0,0,1), and (1,1,1,1) has a minimum distance of 2 to each other? But (0,0,0,1) wouldn't fit, because it has a minimum distance of 1? This is an application of Hamming Distance.

### Re: Combinatorics with minimum "distance"

Can you clarify what you mean by "combinations" and "distance"?

If, rather than in Eebster's case, only (1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1) and (0,0,1,1) are allowed (for orderings of 2+2 indistinguishable items) and "distance" is indeed the hamming distance (d), then the whole set is valid for 0≤d≤2 and any opposing pair is valid for 2<d≤4.

I believe you can construct these sets by starting with any element (the easiest is of course (1,1,0,0) or m ones followed by n zeroes) and swapping any 0 with a 1 (or two distinct swaps if d>2 or three distinct swaps if d>4 or ceil(d/2) swaps in general) to get a new element. Repeat this with any of the current elements while checking that a new candidate element has a hamming distance of at least d from all current elements until you can't find any such element.

My very rigorous argument is that the combinations is nicely symmetrical, therefore every element is part of at least one maximum set and hopefully every set your generate (keeping the distance minimal along the way) is a maximum set.

More generally, you can represent all the combinations as nodes on a graph and draw edges between each pair if the distance between them is at least d, then find a maximum clique. But that is one of those hard problems, so a shortcut would be appreciated.

If, rather than in Eebster's case, only (1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1) and (0,0,1,1) are allowed (for orderings of 2+2 indistinguishable items) and "distance" is indeed the hamming distance (d), then the whole set is valid for 0≤d≤2 and any opposing pair is valid for 2<d≤4.

I believe you can construct these sets by starting with any element (the easiest is of course (1,1,0,0) or m ones followed by n zeroes) and swapping any 0 with a 1 (or two distinct swaps if d>2 or three distinct swaps if d>4 or ceil(d/2) swaps in general) to get a new element. Repeat this with any of the current elements while checking that a new candidate element has a hamming distance of at least d from all current elements until you can't find any such element.

My very rigorous argument is that the combinations is nicely symmetrical, therefore every element is part of at least one maximum set and hopefully every set your generate (keeping the distance minimal along the way) is a maximum set.

More generally, you can represent all the combinations as nodes on a graph and draw edges between each pair if the distance between them is at least d, then find a maximum clique. But that is one of those hard problems, so a shortcut would be appreciated.

### Re: Combinatorics with minimum "distance"

Thanks for the advice guys.

My plan is to just choose a random starting configuration and do random changes + checking validity against all extant configurations.

I was just checking if there is a simple way to estimate how the number of valid combinations changes as I change the number of options.

My plan is to just choose a random starting configuration and do random changes + checking validity against all extant configurations.

I was just checking if there is a simple way to estimate how the number of valid combinations changes as I change the number of options.

### Who is online

Users browsing this forum: No registered users and 15 guests