Calculate Permutation Subsets

0
votes

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}}

2
algorithmpermutation
Please share more details, like your attempts to resolve the problem - Nico Haase
Thank you for your help. Formulating my problem and talking to you helped me find a solution <3 - Koronis Neilos
If I'm not totally wrong, you are searching for a solution to binomial combinations ("n choose k"), not pure permutations. - Vroomfondel
For example: I want to solve a card game with 36 cards where 12 cards are drawn. There are 2 players so everyone gets 6 cards. Now i could solve the game for "n choose k" permutations. The problem is that this would take very long. So I reduce the subset by removing some permutations where i know they do not contribute a different result when calculating the moves needed to win the game. Example: 12 from 36 -> 5.9955562098×10^17 permutations 12 from 36 with the information abstraction ->1.1565501948×10^12 - Koronis Neilos
You mean, it doesn't matter which color I have if my hand consists of, speaking in poker cards: 2,3,4,5,6? An interesting problem. - Vroomfondel

2 Answers

1
votes

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.

1
votes

The solutions is: Divide the subset by two and then find all permutations with increasing elements and then try to find all permutations of the results

Example: 4 from {1,2,3,4,5,6,7,8}

  1. Calc two elements from 8 which leads to {1,2},{1,3} ... {7,8}
  2. Use the results for new permutations {{1,2},{1,3}}, {{1,2},{3,4}}
  3. create an array for every new permutation {1,2,1,3}, {1,2,3,4}
  4. sort it and push it to the results if all the numbers are unique in it ({1,2,1,3} is not valid because it has two ones).

C++ code: (not optimized)
oldSubset

#include <vector>
#include <iostream>
// Requires: sequence from begin to end is sorted
//           middle is between begin and end
template <typename Bidi, typename Functor>
void
for_each_permuted_combination (Bidi begin, Bidi middle, Bidi end, Functor func)
{
  do
    {
      func (begin, middle);
      std::reverse (middle, end);
    }
  while (std::next_permutation (begin, end));
}

std::vector<std::vector<uint8_t> >
oldSubset (int subsetSize, std::vector<uint8_t> setOfNumbers)
{
  if (subsetSize % 2 != 0)
    {
      throw std::logic_error{ "only tested for even subsets" };
      return {};
    }
  auto subsets = std::vector<std::vector<uint8_t> >{};
  for_each_permuted_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize / 2, setOfNumbers.end (), [&subsets] (auto begin, auto end) {
    if (std::is_sorted (begin, end))
      {
        subsets.push_back (std::vector<uint8_t> (begin, end));
      }
  });
  auto permutations = std::vector<std::vector<uint8_t> >{};
  for_each_permuted_combination (subsets.begin (), subsets.begin () + 2, subsets.end (), [&permutations] (auto begin, auto end) {
    auto permutation = std::vector<std::vector<uint8_t> > (begin, end);
    auto possibleResult = std::vector<uint8_t>{};
    std::copy (permutation.front ().begin (), permutation.front ().end (), std::back_inserter (possibleResult));
    std::copy (permutation.back ().begin (), permutation.back ().end (), std::back_inserter (possibleResult));
    auto copyOfPossibleResult = possibleResult;
    std::sort (copyOfPossibleResult.begin (), copyOfPossibleResult.end ());
    if (std::adjacent_find (copyOfPossibleResult.begin (), copyOfPossibleResult.end ()) == copyOfPossibleResult.end ())
      {
        permutations.push_back (possibleResult);
      }
  });
  return permutations;
}

int
main ()
{
  auto results = oldSubset (4, { 1, 2, 3, 4, 5, 6});
    for(auto const& result:results){
        std::copy (result.begin (), result.end (), std::ostream_iterator<int> (std::cout, " "));
        std::cout<<std::endl;
    }
}

output

1 2 3 4 
1 2 3 5 
1 2 3 6 
1 2 4 5 
1 2 4 6 
1 2 5 6 
1 3 2 4 
1 3 2 5 
1 3 2 6 
1 3 4 5 
1 3 4 6 
1 3 5 6 
1 4 2 3 
1 4 2 5 
1 4 2 6 
1 4 3 5 
1 4 3 6 
1 4 5 6 
1 5 2 3 
1 5 2 4 
1 5 2 6 
1 5 3 4 
1 5 3 6 
1 5 4 6 
1 6 2 3 
1 6 2 4 
1 6 2 5 
1 6 3 4 
1 6 3 5 
1 6 4 5 
2 3 1 4 
2 3 1 5 
2 3 1 6 
2 3 4 5 
2 3 4 6 
2 3 5 6 
2 4 1 3 
2 4 1 5 
2 4 1 6 
2 4 3 5 
2 4 3 6 
2 4 5 6 
2 5 1 3 
2 5 1 4 
2 5 1 6 
2 5 3 4 
2 5 3 6 
2 5 4 6 
2 6 1 3 
2 6 1 4 
2 6 1 5 
2 6 3 4 
2 6 3 5 
2 6 4 5 
3 4 1 2 
3 4 1 5 
3 4 1 6 
3 4 2 5 
3 4 2 6 
3 4 5 6 
3 5 1 2 
3 5 1 4 
3 5 1 6 
3 5 2 4 
3 5 2 6 
3 5 4 6 
3 6 1 2 
3 6 1 4 
3 6 1 5 
3 6 2 4 
3 6 2 5 
3 6 4 5 
4 5 1 2 
4 5 1 3 
4 5 1 6 
4 5 2 3 
4 5 2 6 
4 5 3 6 
4 6 1 2 
4 6 1 3 
4 6 1 5 
4 6 2 3 
4 6 2 5 
4 6 3 5 
5 6 1 2 
5 6 1 3 
5 6 1 4 
5 6 2 3 
5 6 2 4 
5 6 3 4

edit: optimized version
subset

#include <vector>
#include <tuple>
#include <iostream>
#include <numeric>
typedef std::tuple<std::vector<u_int8_t>, std::vector<std::vector<u_int8_t> > > subsetAndCombinations;

// Requires: sequence from begin to end is sorted
//           middle is between begin and end
template <typename Bidi, typename Functor>
void
for_each_permuted_combination (Bidi begin, Bidi middle, Bidi end, Functor func)
{
  do
    {
      func (begin, middle);
      std::reverse (middle, end);
    }
  while (std::next_permutation (begin, end));
}

std::vector<std::vector<u_int8_t> >
subsetPermutation (long int subsetSize, std::vector<uint8_t> setOfNumbers)
{
  if (subsetSize % 2 != 0) return {};
  std::vector<std::vector<u_int8_t> > subsets{};
  for_each_permuted_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize / 2, setOfNumbers.end (), [&subsets] (auto begin, auto end) mutable {
    if (std::is_sorted (begin, end))
      {
        subsets.push_back ({ begin, end });
      }
  });
  return subsets;
}


subsetAndCombinations
combinationsFor (std::vector<u_int8_t> const &numbersToCheck, std::vector<std::vector<u_int8_t> > const &subResults, std::vector<u_int8_t> const &numbersToChoseFrom)
{
  auto result = std::tuple<std::vector<u_int8_t>, std::vector<std::vector<u_int8_t> > >{};
  std::get<0> (result) = numbersToCheck;
  std::get<1> (result).reserve (subResults.size ());
  std::vector<u_int8_t> numbers (numbersToChoseFrom.size () - numbersToCheck.size ());
  std::set_difference (numbersToChoseFrom.begin (), numbersToChoseFrom.end (), numbersToCheck.begin (), numbersToCheck.end (), numbers.begin ());
  std::transform (subResults.begin (), subResults.end (), std::back_inserter (std::get<1> (result)), [&numbers] (auto indexes) {
    std::transform (indexes.begin (), indexes.end (), indexes.begin (), [&numbers] (auto index) { return numbers[index]; });
    return indexes;
  });
  return result;
}

std::vector<subsetAndCombinations>
subset (long int k, size_t n)
{
  auto indexes = std::vector<uint8_t> (n);
  std::iota (indexes.begin (), indexes.end (), 0);
  auto results = subsetPermutation (k, indexes);
  auto subResult = subsetPermutation (k, std::vector<uint8_t> (indexes.begin (), indexes.begin () + static_cast<long int> (n) - (k / 2)));
  auto combineResult = std::vector<subsetAndCombinations>{};
  for (auto result : results)
    {
      combineResult.push_back (combinationsFor (result, subResult, indexes));
    }
  return combineResult;
}


int
main ()
{
  auto results = subset (4, 6);
  //print results
  for (auto const &[subset, combis] : results)
    {
      for (auto const &combi : combis)
        {
          std::copy (subset.begin (), subset.end (), std::ostream_iterator<int> (std::cout, " "));
          std::copy (combi.begin (), combi.end (), std::ostream_iterator<int> (std::cout, " "));
          std::cout << std::endl;
        }
      std::cout << std::endl;
    }
}

edit2: benchmark of oldSubset vs subset using catch2 on Intel(R) Core(TM) i5-8600K CPU @ 3.60GHz
clang version 13.0.0 Release build

benchmark name                       samples       iterations    estimated
                                     mean          low mean      high mean
                                     std dev       low std dev   high std dev
-------------------------------------------------------------------------------
subset (4, sixNumbers)                         100             8     4.2488 ms 
                                        5.12302 us    5.11219 us    5.15303 us 
                                        85.5219 ns    37.5917 ns    183.126 ns 
                                                                               
oldSubset (4, sixNumbers)                      100             1     5.3749 ms 
                                        54.1088 us    53.6284 us    55.3097 us 
                                        3.60139 us    1.65755 us    7.04574 us 
                                                                               
subset (4, eightNumbers)                       100             2     4.1362 ms 
                                        20.6127 us    20.3747 us     21.221 us 
                                        1.80225 us    845.815 ns    3.48066 us 
                                                                               
oldSubset (4, eightNumbers)                    100             1    24.4414 ms 
                                        237.982 us     236.57 us    240.066 us 
                                        8.63522 us    6.29346 us    12.1139 us 
                                                                               
subset (6, eightNumbers)                       100             1      4.107 ms 
                                        41.1901 us     41.005 us    41.7309 us 
                                        1.48208 us    634.215 ns    3.21124 us 
                                                                               
oldSubset (6, eightNumbers)                    100             1    149.468 ms 
                                        1.49836 ms    1.49526 ms    1.50226 ms 
                                        17.5873 us    14.9794 us    22.8566 us 
                                                                               
subset (4, tenNumbers)                         100             1     6.5134 ms 
                                        65.0695 us    64.5343 us    65.9829 us 
                                         3.4798 us    2.28411 us    4.82172 us 
                                                                               
oldSubset (4, tenNumbers)                      100             1    74.4154 ms 
                                         754.08 us    752.067 us     756.94 us 
                                        12.1161 us    9.50739 us     15.514 us 
                                                                               
subset (6, tenNumbers)                         100             1    21.2435 ms 
                                        209.317 us    207.847 us    211.412 us 
                                        8.88665 us    6.72703 us    11.1798 us 
                                                                               
oldSubset (6, tenNumbers)                      100             1     1.17232 s 
                                        11.7905 ms    11.7811 ms    11.8024 ms 
                                        53.7095 us    43.4715 us    65.5498 us 
                                                                               
subset (8, tenNumbers)                         100             1    23.4467 ms 
                                        235.972 us    234.262 us    238.712 us 
                                        10.8037 us    7.82671 us    16.3172 us 
                                                                               
oldSubset (8, tenNumbers)                      100             1     6.65554 s 
                                        66.7037 ms    66.5035 ms    66.9362 ms 
                                        1.09843 ms    954.738 us    1.22926 ms 
                                                                               
subset (4, twelveNumbers)                      100             1    14.8182 ms 
                                        149.715 us    148.325 us    152.211 us 
                                        9.22947 us    5.93872 us    14.6366 us 
                                                                               
oldSubset (4, twelveNumbers)                   100             1     204.43 ms 
                                        2.06251 ms    2.05898 ms    2.06644 ms 
                                        18.9013 us    14.9089 us    25.4169 us 
                                                                               
subset (6, twelveNumbers)                      100             1    85.5855 ms 
                                        841.024 us    837.534 us    845.313 us 
                                        19.7371 us    16.5515 us    24.1813 us 
                                                                               
oldSubset (6, twelveNumbers)                   100             1     6.65107 s 
                                        67.0061 ms    66.9113 ms    67.1053 ms 
                                        495.839 us    452.768 us    552.615 us 
                                                                               
subset (8, twelveNumbers)                      100             1    176.525 ms 
                                        1.76037 ms    1.75612 ms    1.76481 ms 
                                        22.2971 us     20.032 us    25.2517 us 
                                                                               
oldSubset (8, twelveNumbers)                   100             1     1.36774 m 
                                          819.4 ms    817.476 ms     821.68 ms 
                                        10.7189 ms    9.24014 ms    12.3794 ms 
                                                                               
subset (10, twelveNumbers)                     100             1    196.563 ms 
                                        1.94786 ms    1.93109 ms    1.96496 ms 
                                         86.618 us    77.6169 us    96.7013 us 
                                                                               
oldSubset (10, twelveNumbers)                  100             1     6.28968 m 
                                         3.83712 s     3.83005 s     3.84504 s 
                                        38.1357 ms    33.2592 ms    44.7012 ms

g++ (GCC) 11.1.0 Release build

benchmark name                       samples       iterations    estimated
                                     mean          low mean      high mean
                                     std dev       low std dev   high std dev
-------------------------------------------------------------------------------
subset (4, sixNumbers)                         100             5     2.2055 ms 
                                        4.39944 us    4.38703 us    4.44751 us 
                                        106.292 ns    11.2639 ns    244.087 ns 
                                                                               
oldSubset (4, sixNumbers)                      100             1     5.2325 ms 
                                        51.7199 us    51.6355 us    51.9248 us 
                                        628.408 ns    315.255 ns    1.25787 us 
                                                                               
subset (4, eightNumbers)                       100             2      3.473 ms 
                                        17.2042 us    17.0591 us    17.8612 us 
                                         1.3454 us     169.46 ns    3.18688 us 
                                                                               
oldSubset (4, eightNumbers)                    100             1     24.246 ms 
                                        243.944 us    243.561 us    244.451 us 
                                        2.23092 us    1.79177 us    2.77771 us 
                                                                               
subset (6, eightNumbers)                       100             1     3.6771 ms 
                                        37.6169 us    37.4309 us    38.1215 us 
                                        1.44523 us    666.679 ns    3.09803 us 
                                                                               
oldSubset (6, eightNumbers)                    100             1    145.011 ms 
                                        1.40323 ms    1.40017 ms    1.40992 ms 
                                        22.0044 us    11.2033 us    39.7721 us 
                                                                               
subset (4, tenNumbers)                         100             1     5.7933 ms 
                                        58.8654 us    58.6273 us    59.5799 us 
                                         1.9226 us    788.588 ns    4.18631 us 
                                                                               
oldSubset (4, tenNumbers)                      100             1    79.7406 ms 
                                        793.094 us    792.263 us    794.172 us 
                                        4.80223 us    3.88654 us    5.93634 us 
                                                                               
subset (6, tenNumbers)                         100             1    18.3623 ms 
                                        188.659 us    188.158 us    190.088 us 
                                        3.97281 us    1.77668 us    8.57928 us 
                                                                               
oldSubset (6, tenNumbers)                      100             1     1.16914 s 
                                        11.6407 ms    11.6321 ms    11.6509 ms 
                                        47.6677 us    39.6378 us    60.7322 us 
                                                                               
subset (8, tenNumbers)                         100             1    22.1842 ms 
                                        222.242 us    221.612 us    223.478 us 
                                        4.32973 us     2.0686 us    8.21289 us 
                                                                               
oldSubset (8, tenNumbers)                      100             1       6.398 s 
                                        63.9016 ms    63.8632 ms    63.9403 ms 
                                        196.147 us    177.473 us    221.609 us 
                                                                               
subset (4, twelveNumbers)                      100             1    12.2964 ms 
                                        124.878 us    124.642 us    125.304 us 
                                        1.57641 us    1.02773 us    2.91879 us 
                                                                               
oldSubset (4, twelveNumbers)                   100             1    219.962 ms 
                                        2.18378 ms     2.1825 ms    2.18628 ms 
                                        8.76462 us    5.40766 us    16.4105 us 
                                                                               
subset (6, twelveNumbers)                      100             1    74.5191 ms 
                                        749.617 us    748.214 us    753.058 us 
                                        10.4827 us    5.42864 us    21.6588 us 
                                                                               
oldSubset (6, twelveNumbers)                   100             1     6.53912 s 
                                        65.2901 ms    65.2766 ms    65.3227 ms 
                                        100.232 us    50.7812 us    201.115 us 
                                                                               
subset (8, twelveNumbers)                      100             1     157.06 ms 
                                        1.58509 ms    1.58038 ms    1.59278 ms 
                                        30.1286 us    21.3724 us    49.5146 us 
                                                                               
oldSubset (8, twelveNumbers)                   100             1     1.30347 m 
                                        775.358 ms    773.562 ms    776.915 ms 
                                        8.46007 ms    7.32211 ms    9.60251 ms 
                                                                               
subset (10, twelveNumbers)                     100             1    189.041 ms 
                                        1.89293 ms    1.88865 ms    1.90194 ms 
                                        30.2312 us    15.9272 us    58.5911 us 
                                                                               
oldSubset (10, twelveNumbers)                  100             1     5.27331 m 
                                         3.14281 s     3.13666 s     3.14754 s 
                                        27.4681 ms    22.0504 ms    33.0537 ms