8

我想知道算法生成长度为 n 的二进制字符串序列，其中下一个字符串以两位数不同。

例如：

11100
11010
11001
10101
10110
10011
00111
01011
01101
01110
11100

当然，必须使用所有n \choose k二进制字符串。

4

3 回答 3

2

我认为您可以使用递归进行设置。

我受到以下身份的启发：

choose(n,k) = choose(n-1,k-1) + choose(n-1,k)

因此，我们定义了一个函数 F(n,k)，它产生所请求的序列（即，长度为 n 的二进制字符串序列，恰好设置了 k 位，使得连续的字符串相差两位）。

首先，观察我们可以以任何我们喜欢的方式重新排序 F(n,k) 的列，并产生另一个同样有效的 F(n,k)。

上面的恒等式表明我们使用 F(n-1,k-1) 和 F(n-1,k) 构建 F(n,k)。令 A 是通过重新排序 F(n-1,k-1) 的列获得的字符串，以便最后一个字符串以 k-1 1s 结尾，然后将 a 添加1到每个字符串。令 B 是通过重新排序 F(n-1,k) 的列获得的字符串，使第一个字符串以 k 1s 结尾，然后将 a 添加0到每个字符串。那么 F(n,k) 只是 A 和 B 的串联。结果是有效的 F(n,k)，因为在 A 和 B 内部，字符串相差两位，A 的最后一个字符串和第一个字符串B 的字符串相差两位（第 k+1 到最后一位和最后一位）。

我将展示一个使用 n=5,k=2 的示例。我们通过递归得到以下两个F序列：

F(4,1): 0001
        0010
        0100
        1000

F(4,2): 0011
        0101
        1001
        1010
        0110
        1100

要制作 A，交换 F(4,1) 的第一列和最后一列并添加1到每个：

A: 10001
   00101
   01001
   00011

要生成 B，不需要列交换，因此我们只需在0F(4,2) 的每一行添加 a：

B: 00110
   01010
   10010
   10100
   01100
   11000

那么 F(5,2) 就是 A 和 B 的串联。

于 2012-08-01T04:54:21.593 回答
2

您应该阅读我关于这种排列（除其他外）的博客文章以获取更多背景信息 - 并点击那里的一些链接。

这是我的词典排列生成器的一个版本，它按照 Steinhaus-Johnson-Trotter 排列生成器的生成顺序制作，按要求执行：

def l_perm3(items):
    'Generator yielding Lexicographic permutations of a list of items'
    if not items:
        yield [[]]
    else:
        dir = 1
        new_items = []
        this = [items.pop()]
        for item in l_perm(items):
            lenitem = len(item)
            try:
                # Never insert 'this' above any other 'this' in the item 
                maxinsert = item.index(this[0])
            except ValueError:
                maxinsert = lenitem
            if dir == 1:
                # step down
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem, -1, -1)
                                 if i <= maxinsert]:
                    yield new_item                    
            else:    
                # step up
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem + 1)
                                 if i <= maxinsert]:
                    yield new_item                    
            dir *= -1

from math import factorial
def l_perm_length(items):
    '''\
    Returns the len of sequence of lexicographic perms of items. 
    Each item of items must itself be hashable'''
    counts = [items.count(item) for item in set(items)]
    ans = factorial(len(items))
    for c in counts:
        ans /= factorial(c)
    return ans

if __name__ == '__main__':
    n = [1, 1, 1, 0, 0]
    print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
    for i, x in enumerate(l_perm3(n[:])):
        print('%3i %r' % (i, x))
    assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'

上述程序的输出例如如下：

Lexicograpic Permutations of 5 items: [1, 1, 1, 0, 0]
  0 [1, 1, 1, 0, 0]
  1 [1, 1, 0, 1, 0]
  2 [1, 0, 1, 1, 0]
  3 [0, 1, 1, 1, 0]
  4 [0, 1, 1, 0, 1]
  5 [1, 0, 1, 0, 1]
  6 [1, 1, 0, 0, 1]
  7 [1, 0, 0, 1, 1]
  8 [0, 1, 0, 1, 1]
  9 [0, 0, 1, 1, 1]
于 2012-08-01T05:09:20.763 回答
0
  1. 采用格雷码 （每个连续数字相差一位的序列）。
  2. 预先添加另一个位并在0和之间循环1。
0000
1001
0011
1010
0110
1111
0101
1100

这将恰好生成一半的 n 位字符串。这是你能得到的最多 - 另一半无法生成，因为例如，从一串 all 0's 开始并一次更改两位，总会有偶数个1's。

于 2012-07-31T16:55:57.820 回答