0

I need to iterate all different "Connect-Four" games possible.
The grid has 42 cells, and there are 21 red and 21 yellow pieces.
Every game generated must use every pieces, and all pieces of the same color are indistinguishable (e.g if you swap two reds in a solution, it doesn't count as another solution)

From that I can draw the conclusion that there's

42!/21!*21! = 538257874440 possible games

I'm thinking about generating binary strings containing 21 0 and 21 1 but beside generating every 42-char long binary string and testing them one by one, I don't have any idea how to do that. That would be 42! (1.4050061e+51) string to test, so that's not an option.

How would you go about generating all these possible games ?

Souk21
  • 91
  • 1
  • 7
  • 3
    Does it matter that, practically, most of these (final) configurations cannot appear, because they involve 4 connected pieces (and thus, the game would have ended earlier)? – Marco13 Feb 07 '17 at 19:20
  • You're asking how to enumerate all 21-sized subsets of a set of size 42? That is a dupe of: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – Paul Hankin Feb 07 '17 at 19:21
  • (Also, you might think 42! is too large, but choose(42, 21) is also large, and very probably too large for you to handle). – Paul Hankin Feb 07 '17 at 19:23
  • @Marco13 It doesn't matter in this situation. – Souk21 Feb 07 '17 at 19:46
  • @PaulHankin Thank you, but the question you're linking is about combinaisons and not permutations – Souk21 Feb 07 '17 at 19:47
  • @Souk21 That's what `42!/21!21!` is, right? Combinations? – beaker Feb 07 '17 at 19:58
  • @beaker I think it's a [distinguishable permutation](http://math.info/Algebra/Distinguishable_Permutations/) – Souk21 Feb 07 '17 at 20:19
  • @Souk21 It's the number of combinations of 42 cells in which 21 of them are red (and the others yellow). Distinguishable permutations are merely a generalization of combinations for more than 2 classes. (Or, perhaps, combinations are merely distinguishable permutations with only 2 classes. Whichever you prefer.) – beaker Feb 07 '17 at 20:21
  • I can imagine two equivalent approaches here: You could either take a vector consisting of 21 `0`s and 21 `1`s, and compute all permutations of this vector. Alternatively you could take the vector `(0...41)`, and compute all subsets of size 21 of this vector (which then would be the positions, for example, of the red player). For the latter, you could use a [`new ChoiceIterable(21, listWith0to41);`](https://github.com/javagl/Combinatorics/blob/master/src/main/java/de/javagl/utils/math/combinatorics/ChoiceIterable.java), but there may also be better solutions. – Marco13 Feb 07 '17 at 20:24
  • Surely some combinations are invalid, like having only yellow pieces on the two bottom rows? No game play could give that result. – m69's been on strike for years Feb 10 '17 at 21:43

1 Answers1

0

It seems that you do not care that some of these games will have ended early. To simply generate all of the possible combinations, you should think of the board as a matrix, where a 1 represents a black, and a 0 represents a red. Now if we vectorize the matrix of values for a full board, then we will get something like 

[0,1,1,0,...]

where the exact order depends on the permutation. Now since we have 21 of each color, that means that you are essentially asking for all of the possible permutations of the vector

[ones(1,21),zeros(1,21)]

(in Matlab and Python notation). In Matlab, you would then generate the list of all permutations by using the function 

perms([ones(1,21),zeros(1,21)])

I am not sure what you want here because obviously it is not feasible to enumerate all of these in practice. If you are just interested in how to do it, I would suggest that you look in the Matlab implementation. It looks like 10 lines of pretty simple code.

bremen_matt
  • 6,902
  • 7
  • 42
  • 90