生成循环的一系列字符的所有唯一顺序(所有循环排列) [英] Generating all unique orders of looping series of characters (all circular permutations)

问题描述

• 我有一个由 Xs 和 Ys 组成的字符串.

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

为了回答这个问题，我们假设此字符串是由Four-X和Two-Y构成的:

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

XXYYYY

如果通过循环而不是不认为唯一的字符串，我如何生成由四个-X和两个-Y组成的所有可能的唯一字符串(/旋转/移位)它周围的字符会产生一个已经找到的字符串?

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?

例如:

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

注意::字符的顺序保持不变，唯一改变的是起始字符(原始字符串以1开头，第二字符串以6开头，第三字符串以4开头.但他们都保留顺序).

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).

在2X和4Y(我们的示例)的情况下，所有可能的唯一排列都是:

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

XXYYYY
XYXYYY
XYYXYY

其他所有订单将是这3个订单之一的转移版本.

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

如何生成N个Xs和M个Ys的字符串的所有可能排列?

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

推荐答案

本质上，您需要生成带有固定数量的二进制项链的组合对象

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

这是从 Sawada文章改编而成的Python代码生成内容固定的项链."
(我使用了最简单的变体，还有更多优化的变体)

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]

这篇关于生成循环的一系列字符的所有唯一顺序(所有循环排列)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！