|
A combinatorial problem
My knowledge of combinatorics is not good enough to solve the following problem. Can anyone help?
I want to find sets of 12-bit integers with the constraint that for every x_i and x_j in the set with i != j, weight(x_i EXOR x_j) >= c where c is a specified parameter. The function weight(x) is defined as the number of set bits in x. For instance, this set of 15 integers satisfies the constraint for c=6: { 0x467, 0xDAE, 0xEDA, 0xB43, 0x3F0, 0xB1C, 0x879, 0x611, 0x19B, 0xAB7, 0xDD5, 0x2CD, 0x880, 0x22A, 0x548} and this set of 21 satisfies the constraint for c=5: { 0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0, 0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21, 0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}. I've found a set of 64 for c=4. The problem is: what is the maximum size of an admissible set as a function of c and how can a set of maximum size be constructed? Paul BTW, the sets given above are [i]not[/i] optimal. |
[QUOTE=xilman;201899]My knowledge of combinatorics is not good enough to solve the following problem. Can anyone help?
I want to find sets of 12-bit integers with the constraint that for every x_i and x_j in the set with i != j, weight(x_i EXOR x_j) >= c where c is a specified parameter. The function weight(x) is defined as the number of set bits in x. For instance, this set of 15 integers satisfies the constraint for c=6: { 0x467, 0xDAE, 0xEDA, 0xB43, 0x3F0, 0xB1C, 0x879, 0x611, 0x19B, 0xAB7, 0xDD5, 0x2CD, 0x880, 0x22A, 0x548} and this set of 21 satisfies the constraint for c=5: { 0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0, 0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21, 0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}. I've found a set of 64 for c=4. The problem is: what is the maximum size of an admissible set as a function of c and how can a set of maximum size be constructed? Paul BTW, the sets given above are [i]not[/i] optimal.[/QUOTE] This is a variation of the "Postage Stamp" problem. See Richard Guy's book on "Unsolved Problems in Number Theory". Constructing such sets is a theoretically hard problem. |
The literature on error correcting codes may have the solutions tabulated. In that language each of your integers is a code word, and you are specifying the minimum distance between code words. Distance c=6 could correct triple errors, distance c=5 could detect triple errors and correct double errors.
|
Does this set of 128 work for c=4?
[CODE]0x000 0x00F 0x033 0x03C 0x055 0x05A 0x066 0x069 0x096 0x099 0x0A5 0x0AA 0x0C3 0x0CC 0x0F0 0x0FF 0x303 0x30C 0x330 0x33F 0x356 0x359 0x365 0x36A 0x395 0x39A 0x3A6 0x3A9 0x3C0 0x3CF 0x3F3 0x3FC 0x505 0x50A 0x536 0x539 0x550 0x55F 0x563 0x56C 0x593 0x59C 0x5A0 0x5AF 0x5C6 0x5C9 0x5F5 0x5FA 0x606 0x609 0x635 0x63A 0x653 0x65C 0x660 0x66F 0x690 0x69F 0x6A3 0x6AC 0x6C5 0x6CA 0x6F6 0x6F9 0x906 0x909 0x935 0x93A 0x953 0x95C 0x960 0x96F 0x990 0x99F 0x9A3 0x9AC 0x9C5 0x9CA 0x9F6 0x9F9 0xA05 0xA0A 0xA36 0xA39 0xA50 0xA5F 0xA63 0xA6C 0xA93 0xA9C 0xAA0 0xAAF 0xAC6 0xAC9 0xAF5 0xAFA 0xC03 0xC0C 0xC30 0xC3F 0xC56 0xC59 0xC65 0xC6A 0xC95 0xC9A 0xCA6 0xCA9 0xCC0 0xCCF 0xCF3 0xCFC 0xF00 0xF0F 0xF33 0xF3C 0xF55 0xF5A 0xF66 0xF69 0xF96 0xF99 0xFA5 0xFAA 0xFC3 0xFCC 0xFF0 0xFFF [/CODE] |
And this set of 16 for c=6:
[CODE]0x000 0x0FF 0x356 0x3A9 0x563 0x59C 0x635 0x6CA 0x93A 0x9C5 0xA6C 0xA93 0xC59 0xCA6 0xF0F 0xFF0 [/CODE] Neither of them are "proven" optimal |
[QUOTE=xilman;201899]My knowledge of combinatorics is not good enough to solve the following problem. Can anyone help?
I want to find sets of 12-bit integers with the constraint that for every x_i and x_j in the set with i != j, weight(x_i EXOR x_j) >= c where c is a specified parameter. The function weight(x) is defined as the number of set bits in x. For instance, this set of 15 integers satisfies the constraint for c=6: { 0x467, 0xDAE, 0xEDA, 0xB43, 0x3F0, 0xB1C, 0x879, 0x611, 0x19B, 0xAB7, 0xDD5, 0x2CD, 0x880, 0x22A, 0x548} and this set of 21 satisfies the constraint for c=5: { 0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0, 0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21, 0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}. I've found a set of 64 for c=4. The problem is: what is the maximum size of an admissible set as a function of c and how can a set of maximum size be constructed? Paul BTW, the sets given above are [i]not[/i] optimal.[/QUOTE] How about an approach like this to find a set: find the weights of all combinations x_i, x_j (which is 2048*4095 combinations for 12 bits). Then find all the pairs with weight >= c, and find the cliques in this set. Chris |
[url]http://www.win.tue.nl/~aeb/codes/binary-1.html[/url]
|
[QUOTE=axn;201919]And this set of 16 for c=6:
[CODE]0x000 0x0FF 0x356 0x3A9 0x563 0x59C 0x635 0x6CA 0x93A 0x9C5 0xA6C 0xA93 0xC59 0xCA6 0xF0F 0xFF0 [/CODE] Neither of them are "proven" optimal[/QUOTE]Thanks. The second is certainly not optimal, as shown by this set of 19 with weight 6: {0x000, 0x5C3, 0x70E, 0x26B, 0xD94, 0xFFF, 0x3E4, 0x6D8, 0x476, 0x927, 0x95A, 0xC4D, 0xA3C, 0x8F1, 0xCAA, 0xB89, 0x09F, 0xE13, 0x539} Curiously enough, my current best set for weight 5 has only 23 members. Surely it must be possible to do much better than that! My algorithm is very simple-minded: start with x_0 equal to zero and then randomly select integers which meet the weight criterion for all previously selected values. When a preset total of calls to random() have been made, start again. Weights of (14, 20, 55) are very easy to find. Extending those limits becomes ever harder. I've spent perhaps 4 cpu-hours on a MacBook Pro to find the best so far. I won't spend much more before giving up and moving to a better algorithm (or just giving up). I'm well aware that back-tracking is a better systematic approach. I've just not yet got around to implementing it. Paul |
A set should remain valid or invalid if you permute the bit indices, so you could start with a set containing 0 and 0...01...1[SUB]b[/SUB], where the latter has at least [I]c[/I] 1's.
Alex |
for c=5, greedy algorithm yielded 25
[CODE]0 31 227 374 440 461 620 693 730 1145 1198 1236 1795 1820 2016 2047 2341 2378 2451 2603 2641 2694 3122 3143 3209[/CODE] EDIT:- 26 [code]0 31 231 377 698 803 846 981 1138 1244 1427 1453 1589 1739 1816 2016 2156 2225 2358 2498 2643 2953 3115 3397 3718 4095 [/code] |
[QUOTE=akruppa;201939]at least [I]c[/I] 1's.[/QUOTE]
This can be changed to "exactly c 1's." (using the assertion that, in a c-optimal solution, there will be at least one pair whose weight is exactly c. if such a pair doesn't exist, then a c-optimal solution will also be a c+1 optimal solution) |
24 for c=6 (should be optimal per wpolly's link)
[CODE]0 63 455 729 876 946 1258 1393 1436 1622 1701 1803 2292 2394 2473 2659 2702 2837 3149 3219 3366 3640 4032 4095 [/CODE] |
[QUOTE=axn;201940]for c=5, greedy algorithm yielded 25
[CODE]0 31 227 374 440 461 620 693 730 1145 1198 1236 1795 1820 2016 2047 2341 2378 2451 2603 2641 2694 3122 3143 3209[/CODE] EDIT:- 26 [code]0 31 231 377 698 803 846 981 1138 1244 1427 1453 1589 1739 1816 2016 2156 2225 2358 2498 2643 2953 3115 3397 3718 4095 [/code][/QUOTE]An exhaustive search via a backtracking algorithm has turned up many examples with 26 members. As noted by akruppa, one would expect there to be many such sets if at least one exists. No examples with 27 have yet been found in a few minutes of computation. My program has been written in a hurry and can doubtless be improved. However, the size of the search space is so large that it can probably not be searched exhaustively. I may continue to optimize my search on the algorithmic level. There is no great point in fiddling with compiler options, and the like as that will give at most a constant speed-up. It's gratifying to see that so much interest has been shown in this problem. Paul |
[QUOTE=xilman;201950]An exhaustive search via a backtracking algorithm has turned up many examples with 26 members. As noted by akruppa, one would expect there to be many such sets if at least one exists. No examples with 27 have yet been found in a few minutes of computation.[/QUOTE]
Unless I misunderstood the link -- and I may have -- optimal should be 32 for c = 5 (and 144 and 24 for 4 and 6, respectively). That's significantly larger. |
[QUOTE=CRGreathouse;201951]Unless I misunderstood the link -- and I may have -- optimal should be 32 for c = 5 (and 144 and 24 for 4 and 6, respectively). That's significantly larger.[/QUOTE]
Yes, that's correct. Seeing the references I think some of the results found by nonlinear programming. Here is my guess for this: if u and v are bits then [code] u xor v=u+v-2*u*v [/code] This would give an NLP problem for 24*12=288 binary variables for c=6 (12 bits for each number) to find the optimal solution. Writing down the system is trivial, maybe solvable. (Obviously you can reduce the number of variables by the above tricks.) |
See also [url]http://www.research.att.com/~njas/codes/And/[/url]
|
Paul, are you still interested in better results? I've found 1 set of size 27 and 4 of size 28 for c=5. Are you interested in results for c=4 (or 3)? Also, I think I wrote my program correctly, but could someone verify my results so I can be sure.
Size=27, c=5 [CODE] 0x000,0x01f,0x0e7,0x1b1,0x1cc, 0x26a,0x2d9,0x336,0x474,0x52b, 0x5d2,0x683,0x6ac,0x718,0x745, 0x7ff,0x8ba,0x943,0x97d,0xa25, 0xad6,0xb8f,0xbe0,0xc4e,0xc95, 0xce9,0xda6 [/CODE] Size=28, c=5 [CODE] 0x000,0x01f,0x0e7,0x1b1,0x1cc, 0x26a,0x2d9,0x336,0x474,0x52b, 0x5d2,0x683,0x6ac,0x718,0x745, 0x7ff,0x8ba,0x943,0x97d,0xa25, 0xad6,0xb8f,0xbe0,0xc4e,0xc95, 0xce9,0xda6,0xe73 0x000,0x01f,0x0e7,0x1b1,0x1cc, 0x26a,0x2d9,0x336,0x474,0x52b, 0x5d2,0x683,0x6ac,0x718,0x745, 0x7ff,0x978,0xa94,0xb2d,0xb53, 0xb8a,0xc49,0xcba,0xd06,0xd9d, 0xe31,0xe5e,0xfe0 0x000,0x01f,0x0e7,0x1b2,0x1cc, 0x269,0x2da,0x335,0x474,0x52b, 0x5d1,0x683,0x6ac,0x718,0x746, 0x7ff,0x8b9,0x943,0x97e,0xa26, 0xad5,0xb8f,0xbe0,0xc4d,0xc96, 0xcea,0xda5,0xe73 0x000,0x01f,0x0e7,0x1b2,0x1cc, 0x269,0x2da,0x335,0x474,0x52b, 0x5d1,0x683,0x6ac,0x718,0x746, 0x7ff,0x978,0xa94,0xb2e,0xb53, 0xb89,0xc4a,0xcb9,0xd05,0xd9e, 0xe32,0xe5d,0xfe0 [/CODE] |
[quote=WraithX;208026]Paul, are you still interested in better results? I've found 1 set of size 27 and 4 of size 28 for c=5. Are you interested in results for c=4 (or 3)? Also, I think I wrote my program correctly, but could someone verify my results so I can be sure.
Size=27, c=5 [code] 0x000,0x01f,0x0e7,0x1b1,0x1cc, 0x26a,0x2d9,0x336,0x474,0x52b, 0x5d2,0x683,0x6ac,0x718,0x745, 0x7ff,0x8ba,0x943,0x97d,0xa25, 0xad6,0xb8f,0xbe0,0xc4e,0xc95, 0xce9,0xda6 [/code]Size=28, c=5 [code] 0x000,0x01f,0x0e7,0x1b1,0x1cc, 0x26a,0x2d9,0x336,0x474,0x52b, 0x5d2,0x683,0x6ac,0x718,0x745, 0x7ff,0x8ba,0x943,0x97d,0xa25, 0xad6,0xb8f,0xbe0,0xc4e,0xc95, 0xce9,0xda6,0xe73 0x000,0x01f,0x0e7,0x1b1,0x1cc, 0x26a,0x2d9,0x336,0x474,0x52b, 0x5d2,0x683,0x6ac,0x718,0x745, 0x7ff,0x978,0xa94,0xb2d,0xb53, 0xb8a,0xc49,0xcba,0xd06,0xd9d, 0xe31,0xe5e,0xfe0 0x000,0x01f,0x0e7,0x1b2,0x1cc, 0x269,0x2da,0x335,0x474,0x52b, 0x5d1,0x683,0x6ac,0x718,0x746, 0x7ff,0x8b9,0x943,0x97e,0xa26, 0xad5,0xb8f,0xbe0,0xc4d,0xc96, 0xcea,0xda5,0xe73 0x000,0x01f,0x0e7,0x1b2,0x1cc, 0x269,0x2da,0x335,0x474,0x52b, 0x5d1,0x683,0x6ac,0x718,0x746, 0x7ff,0x978,0xa94,0xb2e,0xb53, 0xb89,0xc4a,0xcb9,0xd05,0xd9e, 0xe32,0xe5d,0xfe0 [/code][/quote]Your results are impressive but, sadly, I no longer need them for my work. Thanks all the same. Paul |
Bummer, because I found 2 sets of size 139 for c=4 over night. I'll keep running them for a little while to see if I can come up with the maximum sized sets for c=4 (144) and c=5 (32). If I find anything better, I'll post them here.
Here are the two sets of size 139 for c=4: [CODE] 0x000,0x00f,0x03a,0x055,0x066,0x069,0x096,0x0a3,0x0bd,0x0cc, 0x0db,0x0f0,0x113,0x11c,0x125,0x14a,0x17f,0x189,0x1ae,0x1c7, 0x219,0x22c,0x237,0x243,0x25e,0x285,0x28a,0x2ef,0x306,0x32b, 0x330,0x34d,0x39f,0x3c0,0x3f3,0x3fc,0x431,0x452,0x47c,0x498, 0x4a4,0x4c1,0x4ea,0x4f7,0x522,0x544,0x559,0x595,0x5bb,0x5de, 0x5ed,0x614,0x648,0x665,0x67b,0x693,0x6a9,0x6be,0x6c6,0x6dd, 0x701,0x71a,0x73d,0x757,0x76e,0x78c,0x7a7,0x7cb,0x834,0x858, 0x873,0x891,0x8a8,0x8c2,0x8e5,0x8fe,0x939,0x941,0x956,0x96c, 0x984,0x99a,0x9b7,0x9dd,0x9eb,0xa12,0xa21,0xa44,0xa6a,0xa7d, 0xa9c,0xaa6,0xabb,0xac9,0xad7,0xb08,0xb15,0xb3e,0xb5b,0xb67, 0xb83,0xbad,0xbce,0xc03,0xc0c,0xc3f,0xc60,0xcb2,0xccf,0xcd4, 0xcf9,0xd10,0xd75,0xd7a,0xda1,0xdbc,0xdc8,0xdd3,0xde6,0xe38, 0xe51,0xe76,0xe80,0xeb5,0xeda,0xee3,0xeec,0xf0f,0xf24,0xf33, 0xf42,0xf5c,0xf69,0xf96,0xf99,0xfaa,0xfc5,0xff0,0xfff 0x000,0x00f,0x03a,0x055,0x066,0x069,0x096,0x0a3,0x0bd,0x0cc, 0x0db,0x113,0x11c,0x125,0x14a,0x170,0x17f,0x189,0x1ae,0x1c7, 0x219,0x22c,0x237,0x243,0x25e,0x285,0x28a,0x2b0,0x2ef,0x306, 0x32b,0x34d,0x39f,0x3c0,0x3f3,0x3fc,0x431,0x452,0x47c,0x498, 0x4a4,0x4c1,0x4ea,0x4f7,0x522,0x544,0x559,0x595,0x5bb,0x5de, 0x5ed,0x614,0x648,0x665,0x67b,0x693,0x6a9,0x6be,0x6c6,0x6dd, 0x701,0x71a,0x73d,0x757,0x76e,0x78c,0x7a7,0x7cb,0x834,0x858, 0x873,0x891,0x8a8,0x8c2,0x8e5,0x8fe,0x939,0x941,0x956,0x96c, 0x984,0x99a,0x9b7,0x9dd,0x9eb,0xa12,0xa21,0xa44,0xa6a,0xa7d, 0xa9c,0xaa6,0xabb,0xac9,0xad7,0xb08,0xb15,0xb3e,0xb5b,0xb67, 0xb83,0xbad,0xbce,0xc03,0xc0c,0xc3f,0xc60,0xcb2,0xccf,0xcd4, 0xcf9,0xd10,0xd75,0xd7a,0xda1,0xdbc,0xdc8,0xdd3,0xde6,0xe38, 0xe51,0xe76,0xe80,0xeb5,0xeda,0xee3,0xeec,0xf0f,0xf24,0xf33, 0xf42,0xf5c,0xf69,0xf96,0xf99,0xfaa,0xfc5,0xff0,0xfff [/CODE] |
| All times are UTC. The time now is 20:39. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.