Context: I want to solve a card game. To reduce the possible games to calculate I use information abstraction. Which leads to a subset of permutations. Calculating the subset is the problem.
Example: Given 2 players and every player gets 2 cards from a deck of 8 cards. There are 1680 permutations. Some permutations leading to the same game and can be removed from the list of games to calculate for example: {1,2,3,4} , {1,2,4,3} , {2,1,3,4} , {2,1,4,3} all lead to the same game because it does not matter in which order the player receives the cards all that matters is what cards he got. So I can remove the permutations which not fulfill: {a,b,c,d} a<b and c<d. Formula with slider to play around.
My problem is to find a algorithm which produces this subset and is flexible so I can calculate 4 cards from 8 and 6 cards from 12 without changing.
Edit: Currently I try to divide the subset by two and then find all permutations with increasing elements and then I try to find all permutations of the result for size 2
Example: 2 from {1,2,3,4,5,6,7,8} {1,2},{1,3}, {7,8} Use the results for new permutations taking 2 from all the results ignoring equal numbers. Possible results: {{1,2},{3,4}} {{3,4},{1,2}}
This is a solution in Python - sorry, don't have the time to write it in C++. The foo generator is taking the number of cards total and the sum of cards given to the players where it is assumed that every player receives the same number of cards. It then produces the next combination on each iteration.
The del_elmts and restore_elmts functions are just there to avoid copying the whole array P into a temporary when removing the hand of player 1 from the deck. Caveat: Python nevertheless makes a nearly full copy by the [:n-k//2] range access, but in C++ you can avoid that by making the combination function a bit smarter.
import itertools
def del_elmts(li,delset):
for i in range(len(delset)-1,-1,-1):
if (delset[i] < len(li)-len(delset)):
li[delset[i]] = li[len(li)-len(delset)+i]
def restore_elmts(li,delset):
for i in delset:
li[i] = i
def foo(n,k):
if k % 2 != 0: raise ValueError
P = list(range(n))
for p in itertools.combinations(P,k//2):
del_elmts(P,p)
for p2 in itertools.combinations(P[:n-k//2],k//2):
yield p+p2
restore_elmts(P,p)
x = foo(6,4)
for y in x:
print(list(map(lambda x: x+1,y)))
PS: you may need to sort the first and second half of the output if you want to compare it to another algorithm.