0

I have an ordered set, with three subsets; S = (A={1, 5}, B={3, 6}, C={8}). I currently want to figure out how many permutations there are if each permutation step is restricted by subset A or B swapping an element with subset C. While I can figure out this with bruteforce, I came here to get an understanding how a mathematician would tackle this and what is this type of permutation actually called?

Context: I work on a game called Onitama, a board game, where each player has two move cards (subset A and B) and an idle card (subset C). For each turn the player must swap one of their cards with the idle card. A player is free to pick which of their own cards to swap, hence the unordered subsets. I wanted to use permutations to figure out how many turns could be played until the cards returned to their original subsets.

Example steps (of how I assume this would work):

  1. S = (A={1,8}, B={3,6}, C={5})
  2. S = (A={1,8}, B={3,5}, C={6})

  3. S = (A={6,8}, B={3,5}, C={1})

    ...

    N. S = (A={1,5}, B={3,6}, C={8}), back to original order

anders fylling
  • 1
  • Just for clarity, you want to know the number of permutations that can be reached from this starting configuration assuming A and B follow the rules of this game? – forgottenarrow Jul 19 '19 at 23:55
  • That I can bruteforce with a hard proof. I'm interested in how a mathematician expresses the permutations, if there's more info about what I'm doing, etc. I'm interested in learning more about this, as I have no idea how to do this without bruteforcing it. – anders fylling Jul 20 '19 at 00:42
  • 1
    For small problems like this, brute force is fine unless you are interested in some generalization of the problem. The methods you might use would then depend on the generalization you apply.

    For example, suppose A,B and C are assumed to have size $k_A,k_B$ and $k_C$ respectively with $k$ total cards. You can try to find conditions under which all permutations can be reached from any initial permutation (I suspect this would be true under fairly simple conditions). Then there are

    $$\binom{k_A}{k}\binom{k_B}{k-k_A},$$

    permutations. Without irreducibility, you'll need more work.

     – forgottenarrow Jul 21 '19 at 20:40

0 Answers0