1

Having the exact same question like Permutation of 2 or more groups while keeping the ordering of the groups, I hope to write a function that could only keep those permutations that stay in order within groups.

However, I wonder if there is any manner to have the permutation on the fly. Currently, I am doing the exclusion in a post-hoc way, i.e. checking each generated permutation if it meets the group ordering criteria. You know, this is not quite scalable since takes so many unnecessary calculations: For two groups (c.f. size n and m), the operation number sums up to (m+n)! instead of (m+n)!/(n!·m!)).

janmarqz
  • 10,538
Jimmy Zhao
  • 205

1 Answers1

0

Split up the permutations on which group the last element comes from. Then you can recursively intertwine the other groups and all but the last element of the chosen group, and add on the last element of the chosen group. This is a lift of (the generalization of) Pascal's identity for two groups: $$\binom{m + n}{m} = \binom{m + n - 1}{m - 1} + \binom{m + n - 1}{m}$$

Not very efficient python code for two lists (which should actually simplify a bit if you generalize to more than two):

def shuffle(a, b):
    if not a:
        yield b
        return
    if not b:
        yield a
        return
    x = a[-1]
    yield from (l + [x] for l in shuffle(a[:-1], b))
    x = b[-1]
    yield from (l + [x] for l in shuffle(a, b[:-1]))
ronno
  • 11,390
  • Thanks, @ronno. I wonder if I can use this piece of code for your permission as part of my GitHub OSS project. I am now committed to the BWS test for scipy package atm. https://github.com/scipy/scipy/pull/18317 – Jimmy Zhao Apr 17 '23 at 19:42
  • I confirm that I asked that :) I am not the leader, we don't have one, but a maintainer ;) SO is by default using CC-BY-SA which is sadly not compatible with BSD. Hence we would just need your consent here. We will give you credit in the form of a comment along the code. (Note that this is still in an early phase of the review and there is no guarantee the code will even end up in the final form of the PR.) – tupui Apr 17 '23 at 19:54
  • @JimmyZhao feel free to use the code in this answer however you want in whatever project. Note however that, as I mention in the answer, I did not consider efficiency at all when writing it, and it was meant to be more or less runnable pseudocode to demonstrate the algorithm I described. I'm not even sure it has the right asymptotics. If meant for serious use, rewriting it to avoid recursion is probably a good starting point. – ronno Apr 17 '23 at 20:32