0
$\begingroup$

Good evening,

As the title explains, I am looking for an algorithm (I'd implement it in Python) to generate all of the combinations for a given basket of X stocks taken Y at a time (order is not relevant and no repetitions allowed) and not sharing more than Z element between one and another.

I have added the extra restriction because my base case is a universe of 50 stocks and combinations of (i.e basket) 10 stocks, which would generate 10 272 278 170 possible baskets. Since I would have to run further analysis on these baskets, it would be computationally impossible.

As such, I have thought about applying a further restriction which would drastically reduce the number of baskets. In practice, for the same concrete example given above (universe of 50 and baskets of 10) I would like to only generate those baskets of 10, that share a maximum of 5 stocks with any single other basket.

I have tried to come up with a generic algorithm to do so (universe of X, basket of Y and minimum different components of Z) but I haven't managed to come up with a proper solution. Maybe this type of restricted combination does have an actual name in specific literature but my google search have been fruitless.

Hope someone has faced and solved that problem successfully or can come up with a great solution for it!

Thanks!

$\endgroup$
6
  • $\begingroup$ Out of curiosity, what are you using this list of combinations for? What are the "stocks" and "baskets"? $\endgroup$ Feb 12 '21 at 22:12
  • $\begingroup$ They are actually financial stocks, and baskets are structured products on combinations of them (the size of which can vary but in the type of product I'm looking at, the standard is usually 10). The other part of my code analyses some market data to generate buy/sell signals but I needed to run it on a large universe of sufficiently different baskets to spot some interesting opportunities (as I don't know beforehand which ones could prove interesting and the brute force method is computationally impossible as I mentioned)! $\endgroup$
    – Jeremy R.
    Feb 15 '21 at 8:51
  • $\begingroup$ Interesting! Well, in case it is of interest, I found a larger system of 3333 baskets with no two having five or more in common. It also samples all of the 50 stocks roughly evenly, which each stock appearing in 500 to 800 baskets. pastebin.com/0VpzYiMc $\endgroup$ Feb 16 '21 at 14:22
  • $\begingroup$ Great, thanks Mike! That will allow me to run it on a much wider scope and potentially spot more interesting combination, much appreciated! Out of curiosity did you come up with those yourself or was it extracted from some paper ? It's quite the interesting branch of maths but I'm afraid I am very limited when it comes to this topic. $\endgroup$
    – Jeremy R.
    Feb 17 '21 at 11:39
  • $\begingroup$ I found it myself. I started $45$ baskets, given by breaking the 50 stocks into 10 groups and picking all ways to choose two of those groups. Then, I looked at all ways to selected $5$ of those groups and take two stocks from each selected group to make a basket of $10$. I looked at these one of a time by brute force, and added them if they created no conflict with previously added baskets. Furthermore, is a way to extend my collection by $3125$ more (nearly doubling it!) by using a "quadratic residue code." $\endgroup$ Feb 17 '21 at 20:22
0
$\begingroup$

What you are looking for in the literature is known as a constant weight binary code (Wikipedia). Specifically, if $A(n,d,w)$ is the maximum number of binary vectors, each with $w$ ones and $n-w$ zeroes, such that the Hamming distance between any two codewords is $d$, then the largest possible size of your set of sets would be $A(X,2(Y-Z) ,Y)$. In the special case you mentioned, you want $A(50,10,10)$.

Not much is known about the exact optimal values of $A(n,d,w)$. The main ways to find constant weight binary codes usually involve a lot of computational effort. This table lists the values of $A(n,10,w)$ for $n\ge 32$ and $w\le 16$, but the highest relevant value for your problem is $A(32,10,10)\ge 500$. This means that even when you restrict yourself to only using the first $32$ elements of your $50$ element set, you can get $500$ sets. If you click on that link, they actually provide the list of codewords.

The question you need to consider is; since there is little hope of finding the maximal collection of subsets of a size of $50$, each with size $10$ and at most $5$ elements in common, how many subsets do you realistically need? Is $500$ enough?

Solution for $315$ subsets of $\{1,\dots,29\}$ of size $5$ where each subset has at most two in common with each other:

01000000000001000100000001010
00000000001000000000101001010
00000000000000000010010001110
00000000000000100001000001011
00000000000101000001001000010
00000000000011000000000000111
01000010000000010000001000010
01000000010000100100100000000
01000000100100001000001000000
00001010000000100000100000010
11001000001000000000001000000
00000100001000110000100000000
01000100000000000000011000001
00000000000100100000101000001
01000100010000011000000000000
01000001000100100000000000010
11000000000000110000000000001
01000010000000001000100001000
00000000010000100010000100010
00100010000100000000010000010
00001000010001000100001000000
00010010010000001000000000100
00000001010010001000000000010
01000000000100000001010001000
00001000000000100010001001000
00000011100000001001000000000
00000010110000000000000001010
00000000100100000010110000000
00001010000000000000001110000
00000010001000001010000000001
00000100010000000000000010011
00000000010100001000010000001
00001001000000000000001000011
00100010000000000010100000100
00000000010001001000000110000
01000010010000000000010010000
00000001010000100001001000000
00000011000000000000110000001
00000000110000000000001100001
00000010000100000000001001100
00001000010000001010100000000
01101000000000000100010000000
00000000001001100000001000100
01000000011010000000000001000
00100101000000100010000000000
00100000000000011001000000010
10100000000001000000000001100
00010000000001011010000000000
01100000000000100000000010100
10000000000001101001000000000
00000110011000000000001000000
00000101010100000000100000000
00001000000000001001011000000
00010100000000000000000011100
00000000000110001011000000000
01110000000000000000001001000
00000000000011100010100000000
00011000011100000000000000000
00001101001010000000000000000
00000000000000001101000101000
00001000100000000000000001101
01100000000000000010000100001
00000000000001100000010010001
00100000011000000000000000101
00000101000001001000000000001
01000000000000001001000010001
10001000000110000000000001000
00101000001000010010000000000
00100000000000010100000100100
01000000000001001000010000100
00100010001000000000000101000
00000100010001000010010000000
00100100000000001000010010000
00000000001100000000000011001
00001100000000000011000000001
00110000000000001100000000001
10000000010000001000001001000
00000001000000010010100000010
00101000000100000001000000100
00001000001001001000000001000
00000010001010000001000000010
00100100010000000100000001000
10000000100000011000010000000
00100010100000100000001000000
10000010010001000000100000000
00001000000010000010010010000
00100000001000000001001010000
01000100000010000000100000100
00100000000100101000000100000
10000001000010010000001000000
01100000100000010000100000000
00001000000001010000100000100
01010000001000001000000100000
10000010000010000000010100000
00100000010000010000011000000
00000101000000010000010000100
00100000100000001010000001000
00000010000001000010000010010
00100000010100000010000010000
00001001000001000001000010000
00000100001000001001000000100
00000100000100001000000001010
10000000000001000010001100000
00010000000000010000110010000
00001100010000100000000000100
10000001001100001000000000000
00000010000011001000001000000
00110000010000000000100000010
00001000000100110000010000000
00100000110001000001000000000
00010011000001000000000001000
00000000100000100011000010000
10000010000000000001000011000
00000100000000000100001000110
00000000000100001100100000100
10010000000000000001001000001
00000000000010010000100001001
00001010000010000100000000001
00000000001000010000010100001
10100000100010000000000000001
00100010000001010000000000001
00000000000000010010000010101
00000110000000000000000100101
10000001100000000000100001000
00001000100010000001100000000
10000000000010000100100000010
10000010001000010000000000100
00000000100010000100001001000
01000100001001000000000010000
00000000001010000010000100100
00100001000000001000001000100
00000000100001001000100000010
01001000000100000000100010000
00001000001000100001000100000
10000100010010000001000000000
00100001000100010000000001000
00000000100000010001001000100
01000100100000100000000001000
10000010000100100010000000000
00100000000010000010001000010
00100000000001000100100010000
00010001001000000000100000100
00000100100010001000000100000
00010000000010001000010001000
01001000100001000010000000000
10000100001000000000010001000
10001000010000010000000010000
00000000010010000100010000100
00000001000000101000100010000
10000000100000000001000100010
00010010000110000000100000000
00101000010010000000000100000
10000000000100010001100000000
01001000000000010000000101000
00000010100001000100000000100
00000001001000100100000001000
10000100100000000010000000100
00100000001010001000100000000
00100100000001000000000100010
10000000001000000010100010000
00000100000000010001000110000
00011000000010000000001000100
01000000001000100010010000000
00100001001001000000010000000
00000010000100011000000010000
01000000010000000010001000100
00001001000000011100000000000
01000000101000000000000000110
00000000001101000000100100000
00011100000000000000010100000
10100000000000000011010000000
00000000000001010000001011000
00000001110000000000000010100
00000000000000111000000001100
11000000000000001010000000010
01100000000111000000000000000
00111000000001100000000000000
00000000011000000001110000000
00000101000000000000001101000
00110100000010010000000000000
01010000000000000011100000000
00000000001110000000011000000
00000000000000110100000010010
10000000010100000000000000110
00010000100100000000000000011
10001000000000000000100100001
10000000000000000110000001001
00000000101000000100100000001
00010001000010100000000000001
00010001000100000000001010000
00010100000100100001000000000
10001000100000100100000000000
00000010100000010010000100000
00010000000000101000001000010
10000000000010001000000010100
01010000000100010000000000100
01001000000010101000000000000
00000010010100000001000100000
00001001010000000000010001000
00000100100000000101010000000
10000000100101000000000010000
00000000010010000000101010000
00100001000000000001100100000
10010100000000001000100000000
00000000000110010000000100010
00010010000000000010011000000
00000001101000000010001000000
10100000001000100000000000010
00011010000000010001000000000
00010000000000100110000000100
00000110100000000000100010000
00000000100001000000010101000
10000100000001010100000000000
00000000000100000000010110100
01010101000000000100000000000
00000000100110100000000000100
00000000010101100000000001000
10011001000000000010000000000
00100000000010100101000000000
00001001100100000000000100000
00000010000000000101101000000
00000000010000000000100101100
10010000000000010000000001010
01000000000010010110000000000
00000000100000000000011010010
00000000101010010000000010000
10101010000000001000000000000
00001010101000000000010000000
00000100000000000110100100000
01100110000000000001000000000
00000001000000001010010100000
00000000011001010000000000010
00000000000000000001100010110
11010010100000000000000000000
00000010010010110000000000000
00000000110100010100000000000
01001011000000000000000000100
00000000001001000111000000000
00100100101100000000000000000
00000000000000011000101100000
01000000000000000000110100010
10110000000000000000000110000
00000000000011010001010000000
10000000000000000000111000100
00000000111000101000000000000
11100001010000000000000000000
00001110000101000000000000000
00000000000000001110001010000
10000111000000000000000000010
00000000000000100100011100000
00000001100001110000000000000
01010000010001000000000000001
00000001000100000101000000001
00010001000000000001010000010
00011000000000000100100001000
10000001000000100000000100100
00010001010000010000000100000
00000010000000100001010000100
00000001000101000010000000100
00000100000001000001100001000
00010100001000000010000000010
00000100000110000100000010000
01000001100010000000010000000
10001000000001000000010000010
00011000100000001000000010000
00010000000100000010000101000
00010000001000010100001000000
01000000100000000100000110000
10000000011000000100000100000
00010000010000000101000010000
10010000010000100000010000000
01000001000001000000101000000
00010000101000000001000001000
00000100000010100000010000010
10100000000100000100001000000
00000001000010000001000001100
00001000000100000110000000010
00010000100000100000100100000
00000110000010000010000001000
00001000001000000100000010100
01000010000001100000000100000
11000100000100000000000100000
00010000110010000010000000000
00100000000000100000110001000
00000001000011000100000100000
00000000010000010011000001000
00001100100000010000000000010
01000010001100000100000000000
00100011000010000000000010000
00001000000000001000000100110
00110000100000000000010000100
01000001000000000010000011000
00000000001000001100010000010
01000000000010000001001100000
10000001000000000100010010000
00010000000001000001000100100
00000100000100010010001000000
01000001001000010001000000000
00010010001000100000000010000
00010010000000000100000100010
00100001100000000100000000010
00010000000101000100010000000
00010100100001000000001000000
01001000010000000001000000010
10000100000000100000001010000
00000010000000010100010001000
00000011010000000110000000000
10010000001011000000000000000
00101100000000000000101000000
11000000000000000101000000100
00000000000010100000000111000
00000110000000101100000000000
00000001001000000000000110010
01010000000010000000000010010
00101000000000000000000011010
$\endgroup$
9
  • $\begingroup$ Thank you Mike for the answer. I have been reading about it and it's much more complex than I first assumed it was. That being said, the highest relevant value A(32,10,10) that you point out and its lower bound would already suffice for my actual application. I am however unclear as to how I could leverage the explicit list of 500 codewords provided and implement it in my specific case. Would you mind further explaining that to me ? Thank you very much anyway for the quick answer! $\endgroup$
    – Jeremy R.
    Feb 11 '21 at 22:34
  • $\begingroup$ Happy to help! You need to convert each codeword from hexadecimal to binary. Each result should be a binary vector with 32 bits and exactly 10 ones, which naturally translates into subsets of $\{1,2,\dots,32\}$. $\endgroup$ Feb 11 '21 at 23:13
  • $\begingroup$ Great Mike, with that I'll be able to implement that case! I was also contemplating looking at a basket of 8 elements with at most 4 elements in common, which would be A(X,8,8) as far as I understand. I am not sure how to process the solution in the link though. Same question for a basket of 5 elements with at most 2 elements in common (X,6,5) and the solution in the link $\endgroup$
    – Jeremy R.
    Feb 12 '21 at 8:32
  • $\begingroup$ For the A(28,8,8) file, the codewords all smushed together instead of on separate lines. So you first need to split that long word into sections of length 7, then convert each hex block to binary to get words of length 28. $\endgroup$ Feb 12 '21 at 14:26
  • $\begingroup$ For the second file, the first several rows represent permutations. Those permutations generate a subgroup, and you need to apply all the permutations in that subgroup to the short list of codewords provided to get the entire list. At least, I am pretty sure... $\endgroup$ Feb 12 '21 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.