Combinatorics with minimum "distance"

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Ciber
Posts: 123
Joined: Fri Mar 15, 2013 1:33 pm UTC

Combinatorics with minimum "distance"

Postby Ciber » Thu Jan 18, 2018 3:52 am UTC

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?

User avatar
Eebster the Great
Posts: 2924
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Combinatorics with minimum "distance"

Postby Eebster the Great » Thu Jan 18, 2018 6:33 am UTC

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.

User avatar
Flumble
Yes Man
Posts: 1990
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Combinatorics with minimum "distance"

Postby Flumble » Thu Jan 18, 2018 3:56 pm UTC

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. :roll:

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.

Ciber
Posts: 123
Joined: Fri Mar 15, 2013 1:33 pm UTC

Re: Combinatorics with minimum "distance"

Postby Ciber » Fri Jan 19, 2018 2:41 am UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests