0
  • I have a string that is made out of Xs and Ys.

For the sake of the question let's say this string is constructed of Four-Xs and Two-Ys: 

XXYYYY

How can I generate all of the possible unique strings that are made out of Four-Xs and Two-Ys given that the string is not considered unique if by looping (/rotating/shifting) its characters around it produces a string that was already found?

For instance:

XXYYYY is considered similar to YXXYYY and YYYXXY (cardinal numbers added clarify)
123456                          612345     456123

Notice: that the order of the characters stays unchanged, the only thing that changed is the starting character (The original string starts with 1, the 2nd string with 6, and the 3rd with 4, but they all keep the order).

In the case of Two-Xs and Four-Ys (our example) all the possible permutations that are unique are:

XXYYYY
XYXYYY
XYYXYY

And every other order would be a shifted version of one of those 3.

How would you generate all of the possible permutation of a string with and N number of Xs and an M number of Ys?

Michael Seltenreich
  • 3,013
  • 2
  • 29
  • 55

1 Answers1

4

Essentially you need to generate combinatorial objects named binary necklaces with fixed number of ones

This is Python code adapted from Sawada article "A fast algorithm to generate necklaces with fixed contents".
(I used the simplest variant, there are also more optimized ones)

n = 6
d = 3
aa = [0] * n
bb = [n - d, d]  #n-d zeros, d ones

def SimpleFix(t, p):
    if t > n:
        if n % p == 0:
            print(aa)
    else:
        for j in range(aa[t - p - 1], 2):
            if bb[j] > 0:
                aa[t - 1] = j
                bb[j] -= 1
                if j == aa[t-p-1]:
                    SimpleFix(t+1, p)
                else:
                    SimpleFix(t+1, t)
                bb[j] += 1

SimpleFix(1, 1)

#example for 3+3

[0, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 1]
[0, 1, 0, 1, 0, 1]
MBo
  • 77,366
  • 5
  • 53
  • 86
  • Very interesting approach! I've seen Sawada's articl and wasn't sure how to adapt it.. I appreciate the help! – Michael Seltenreich Mar 06 '19 at 22:36
  • What if I would like to do the necklace of a list [0,1,2,3,4] rather than just 0 and 1 in your case? What can I do? – Wei Shan Lee Jul 12 '21 at 10:28
  • @LEE WEI SHAN Generate all 24 permutations of `[1,2,3,4]` list and combine with leading `0` – MBo Jul 12 '21 at 12:32
  • @MBo What if I would like to remove the repeated ones? For example, in the case of [0,1,2,3,4], [0,1,2,3,4] is regarded the same as [0,4,3,2,1]. How do I remove one of them? – Wei Shan Lee Jul 12 '21 at 13:03
  • @LEE WEI SHAN Aha, I forgot about reverse order. Cited article of Sawada contains algorithms suitable for non-binary necklaces. k=5 in your case, and counter list is (1,1,1,1,1) – MBo Jul 12 '21 at 13:22
  • @MBo I find out a very interesting class posted here: [LINK](https://codereview.stackexchange.com/questions/225915/fixed-content-necklace-generator?newreg=2ecab2b032e842ad85005a87735097c6) But if I put in n = [1,1,1,1,1] , the algorithm does not remove the cases with reverse orders. Can you comment on how to modify it? – Wei Shan Lee Jul 18 '21 at 14:58
  • @LEE WEI SHAN Sorry, I experimented only with binary necklaces and have no experience with arbitrary k – MBo Jul 18 '21 at 16:22