通过交换两位（不是字典顺序）来排列二进制数
Permutations of binary number by swapping two bits (not lexicographically)
我正在寻找一种算法，该算法计算给定长度 (n) 和位集数量 (k) 的位串的所有排列。例如，当 n=4 和 k=2 算法应输出：
1100
1010
1001
0011
0101
0110
我知道 Gosper 的 Hack 可以按字典顺序生成所需的排列。但我需要它们以这样的方式生成，即两个连续的排列仅在两个（或至少恒定数量的）位位置上有所不同（如上例所示）。
另一个 bithack 这样做会很棒，但算法描述也会对我有很大帮助。
这很容易通过递归实现：
public static void nextPerm(List<Integer> list, int num, int index, int n, int k) {
if(k == 0) {
list.add(num);
return;
}
if(index == n) return;
int mask = 1<<index;
nextPerm(list, num^mask, index+1, n, k-1);
nextPerm(list, num, index+1, n, k);
}
运行 这与客户：
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
nextPerm(list, 0, 0, 4, 2);
}
输出：
0011
0101
1001
0110
1010
1100
想法是从初始数字开始，考虑改变一点，一次一个索引，并记录你改变了多少次位。更改位 k 次后（当 k == 0 时），存储数字并终止分支。
步位算法
要通过在每个步骤中恰好交换一个设置位和一个未设置位来生成二进制序列的排列（即连续排列之间的汉明距离等于二），您可以使用此 "walking bit" 算法；它的工作方式类似于创建（反向）字典顺序，但设置的位交替向右和向左移动，结果序列的某些部分被镜像。这可能用一个例子更好地解释：
递归实现
递归算法将接收一个 n 位序列，设置了 k 位，全部在左侧或全部在右侧。然后它将在末尾保留 1，对序列的其余部分进行递归，移动设置位并在末尾保留 01，对其余位进行递归，移动设置位并将 001 保留在最后，等等......直到最后一次递归只设置位。如您所见，这会创建交替的 left-to-right 和 right-to-left 递归。
当使用仅设置了一个位的序列调用算法时，这是最深的递归级别，设置的位从一端走到另一端。
代码示例 1
这是一个简单的递归 JavaScript 实现：
function walkingBits(n, k) {
var seq = [];
for (var i = 0; i < n; i++) seq[i] = 0;
walk (n, k, 1, 0);
function walk(n, k, dir, pos) {
for (var i = 1; i <= n - k + 1; i++, pos += dir) {
seq[pos] = 1;
if (k > 1) walk(n - i, k - 1, i%2 ? dir : -dir, pos + dir * (i%2 ? 1 : n - i))
else document.write(seq + "<BR>");
seq[pos] = 0;
}
}
}
walkingBits(7,3);
翻译成 C++ 可能是这样的：
#include <iostream>
#include <string>
void walkingBits(int n, int k, int dir = 1, int pos = 0, bool top = true) {
static std::string seq;
if (top) seq.resize(n, '0');
for (int i = 1; i <= n - k + 1; i++, pos += dir) {
seq[pos] = '1';
if (k > 1) walkingBits(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i), false);
else std::cout << seq << '\n';
seq[pos] = '0';
}
if (top) seq.clear();
}
int main() {
walkingBits(7, 3);
}
（另请参阅 [this C++11 version][3]，由 VolkerK 撰写以回答有关上述代码的问题。）
（Rextester好像被黑了，所以我把Volker的代码贴在下面。）
#include <iostream>
#include <vector>
#include <functional>
void walkingBits(size_t n, size_t k) {
std::vector<bool> seq(n, false);
std::function<void(const size_t, const size_t, const int, size_t)> walk = [&](const size_t n, const size_t k, const int dir, size_t pos){
for (size_t i = 1; i <= n - k + 1; i++, pos += dir) {
seq[pos] = true;
if (k > 1) {
walk(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i));
}
else {
for (bool v : seq) {
std::cout << v;
}
std::cout << std::endl;;
}
seq[pos] = false;
}
};
walk(n, k, 1, 0);
}
int main() {
walkingBits(7, 3);
return 0;
}
代码示例 2
或者，如果您更喜欢实际交换数组元素的代码：
function walkingBits(n, k) {
var seq = [];
for (var i = 0; i < n; i++) seq[i] = i < k ? 1 : 0;
document.write(seq + "<BR>");
walkRight(n, k, 0);
function walkRight(n, k, pos) {
if (k == 1) for (var p = pos + 1; p < pos + n; p++) swap(p - 1, p)
else for (var i = 1; i <= n - k; i++) {
[walkLeft, walkRight][i % 2](n - i, k - 1, pos + i);
swap(pos + i - 1, pos + i + (i % 2 ? 0 : k - 1));
}
}
function walkLeft(n, k, pos) {
if (k == 1) for (var p = pos + n - 1; p > pos; p--) swap(p - 1, p)
else for (var i = 1; i <= n - k; i++) {
[walkRight, walkLeft][i % 2](n - i, k - 1, pos);
swap(pos + n - i - (i % 2 ? 1 : k), pos + n - i);
}
}
function swap(a, b) {
var c = seq[a]; seq[a] = seq[b]; seq[b] = c;
document.write(seq + "<BR>");
}
}
walkingBits(7,3);
代码示例 3
此处递归被展开为迭代实现，每个设置位（即每个递归级别）由一个对象 {o,d,n,p} 表示，该对象保存最左边位置的偏移量，方向设置位正在移动，位数（即序列这部分的长度），以及设置位在这部分中的当前位置。
function walkingBits(n, k) {
var b = 0, seq = [], bit = [{o: 0, d: 1, n: n, p: 0}];
for (var i = 0; i < n; i++) seq.push(0);
while (bit[0].p <= n - k) {
seq[bit[b].o + bit[b].p * bit[b].d] = 1;
while (++b < k) {
bit[b] = {
o: bit[b-1].o + bit[b-1].d * (bit[b-1].p %2 ? bit[b-1].n-1 : bit[b-1].p+1),
d: bit[b-1].d * (bit[b-1].p %2 ? -1 : 1),
n: bit[b-1].n - bit[b-1].p - 1,
p: 0
}
seq[bit[b].o + bit[b].p * bit[b].d] = 1;
}
document.write(seq + "<BR>");
b = k - 1;
do seq[bit[b].o + bit[b].p * bit[b].d] = 0;
while (++bit[b].p > bit[b].n + b - k && b--);
}
}
walkingBits(7, 3); // n >= k > 0
将字典顺序转换为步行位
因为步行位算法是生成（反向）字典顺序排列的算法的变体，字典顺序中的每个排列都可以转换为步行位顺序中相应的排列，通过镜像适当的二进制序列的一部分。
因此，您可以使用任何算法（例如 Gosper's Hack）以字典顺序或反向字典顺序创建排列，然后转换每个排列以获得步行位顺序。
实际上，这意味着从左到右遍历二进制序列，如果您在奇数个零之后找到一个设置位，则反转序列的其余部分并从右到左遍历它，依此类推在...
代码示例 4
在下面的代码中，n,k = 7,3 的排列按字典序逆序生成，然后转换为 one-by-one：
function lexi2walk(lex) {
var seq = [], ofs = 0, pos = 0, dir = 1;
for (var i = 0; i < lex.length; ++i) {
if (seq[ofs + pos * dir] = lex[i]) {
if (pos % 2) ofs -= (dir *= -1) * (pos + lex.length - 1 - i)
else ofs += dir * (pos + 1);
pos = 0;
} else ++pos;
}
return seq;
}
function revLexi(seq) {
var max = true, pos = seq.length, set = 1;
while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
if (pos < 0) return false;
seq[pos] = 0;
while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
return true;
}
var s = [1,1,1,0,0,0,0];
document.write(s + " → " + lexi2walk(s) + "<br>");
while (revLexi(s)) document.write(s + " → " + lexi2walk(s) + "<br>");
均匀灰色路径
此算法创建的排列顺序与 D. Knuth 在 The Art of Computer Programming[=114] 中描述的 "homogeneous Gray path for combinations" 算法创建的排列顺序相似，但不完全相同=]卷。 4a，节。 7.2.1.3、式(31)&图26c.
我正在寻找一种算法，该算法计算给定长度 (n) 和位集数量 (k) 的位串的所有排列。例如，当 n=4 和 k=2 算法应输出：
1100
1010
1001
0011
0101
0110
我知道 Gosper 的 Hack 可以按字典顺序生成所需的排列。但我需要它们以这样的方式生成，即两个连续的排列仅在两个（或至少恒定数量的）位位置上有所不同（如上例所示）。 另一个 bithack 这样做会很棒，但算法描述也会对我有很大帮助。
这很容易通过递归实现：
public static void nextPerm(List<Integer> list, int num, int index, int n, int k) {
if(k == 0) {
list.add(num);
return;
}
if(index == n) return;
int mask = 1<<index;
nextPerm(list, num^mask, index+1, n, k-1);
nextPerm(list, num, index+1, n, k);
}
运行 这与客户：
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
nextPerm(list, 0, 0, 4, 2);
}
输出：
0011
0101
1001
0110
1010
1100
想法是从初始数字开始，考虑改变一点，一次一个索引，并记录你改变了多少次位。更改位 k 次后（当 k == 0 时），存储数字并终止分支。
步位算法
要通过在每个步骤中恰好交换一个设置位和一个未设置位来生成二进制序列的排列（即连续排列之间的汉明距离等于二），您可以使用此 "walking bit" 算法；它的工作方式类似于创建（反向）字典顺序，但设置的位交替向右和向左移动，结果序列的某些部分被镜像。这可能用一个例子更好地解释：
递归实现
递归算法将接收一个 n 位序列，设置了 k 位，全部在左侧或全部在右侧。然后它将在末尾保留 1，对序列的其余部分进行递归，移动设置位并在末尾保留 01，对其余位进行递归，移动设置位并将 001 保留在最后，等等......直到最后一次递归只设置位。如您所见，这会创建交替的 left-to-right 和 right-to-left 递归。
当使用仅设置了一个位的序列调用算法时，这是最深的递归级别，设置的位从一端走到另一端。
代码示例 1
这是一个简单的递归 JavaScript 实现：
function walkingBits(n, k) {
var seq = [];
for (var i = 0; i < n; i++) seq[i] = 0;
walk (n, k, 1, 0);
function walk(n, k, dir, pos) {
for (var i = 1; i <= n - k + 1; i++, pos += dir) {
seq[pos] = 1;
if (k > 1) walk(n - i, k - 1, i%2 ? dir : -dir, pos + dir * (i%2 ? 1 : n - i))
else document.write(seq + "<BR>");
seq[pos] = 0;
}
}
}
walkingBits(7,3);
翻译成 C++ 可能是这样的：
#include <iostream>
#include <string>
void walkingBits(int n, int k, int dir = 1, int pos = 0, bool top = true) {
static std::string seq;
if (top) seq.resize(n, '0');
for (int i = 1; i <= n - k + 1; i++, pos += dir) {
seq[pos] = '1';
if (k > 1) walkingBits(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i), false);
else std::cout << seq << '\n';
seq[pos] = '0';
}
if (top) seq.clear();
}
int main() {
walkingBits(7, 3);
}
（另请参阅 [this C++11 version][3]，由 VolkerK 撰写以回答有关上述代码的问题。）
（Rextester好像被黑了，所以我把Volker的代码贴在下面。）
#include <iostream>
#include <vector>
#include <functional>
void walkingBits(size_t n, size_t k) {
std::vector<bool> seq(n, false);
std::function<void(const size_t, const size_t, const int, size_t)> walk = [&](const size_t n, const size_t k, const int dir, size_t pos){
for (size_t i = 1; i <= n - k + 1; i++, pos += dir) {
seq[pos] = true;
if (k > 1) {
walk(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i));
}
else {
for (bool v : seq) {
std::cout << v;
}
std::cout << std::endl;;
}
seq[pos] = false;
}
};
walk(n, k, 1, 0);
}
int main() {
walkingBits(7, 3);
return 0;
}
代码示例 2
或者，如果您更喜欢实际交换数组元素的代码：
function walkingBits(n, k) {
var seq = [];
for (var i = 0; i < n; i++) seq[i] = i < k ? 1 : 0;
document.write(seq + "<BR>");
walkRight(n, k, 0);
function walkRight(n, k, pos) {
if (k == 1) for (var p = pos + 1; p < pos + n; p++) swap(p - 1, p)
else for (var i = 1; i <= n - k; i++) {
[walkLeft, walkRight][i % 2](n - i, k - 1, pos + i);
swap(pos + i - 1, pos + i + (i % 2 ? 0 : k - 1));
}
}
function walkLeft(n, k, pos) {
if (k == 1) for (var p = pos + n - 1; p > pos; p--) swap(p - 1, p)
else for (var i = 1; i <= n - k; i++) {
[walkRight, walkLeft][i % 2](n - i, k - 1, pos);
swap(pos + n - i - (i % 2 ? 1 : k), pos + n - i);
}
}
function swap(a, b) {
var c = seq[a]; seq[a] = seq[b]; seq[b] = c;
document.write(seq + "<BR>");
}
}
walkingBits(7,3);
代码示例 3
此处递归被展开为迭代实现，每个设置位（即每个递归级别）由一个对象 {o,d,n,p} 表示，该对象保存最左边位置的偏移量，方向设置位正在移动，位数（即序列这部分的长度），以及设置位在这部分中的当前位置。
function walkingBits(n, k) {
var b = 0, seq = [], bit = [{o: 0, d: 1, n: n, p: 0}];
for (var i = 0; i < n; i++) seq.push(0);
while (bit[0].p <= n - k) {
seq[bit[b].o + bit[b].p * bit[b].d] = 1;
while (++b < k) {
bit[b] = {
o: bit[b-1].o + bit[b-1].d * (bit[b-1].p %2 ? bit[b-1].n-1 : bit[b-1].p+1),
d: bit[b-1].d * (bit[b-1].p %2 ? -1 : 1),
n: bit[b-1].n - bit[b-1].p - 1,
p: 0
}
seq[bit[b].o + bit[b].p * bit[b].d] = 1;
}
document.write(seq + "<BR>");
b = k - 1;
do seq[bit[b].o + bit[b].p * bit[b].d] = 0;
while (++bit[b].p > bit[b].n + b - k && b--);
}
}
walkingBits(7, 3); // n >= k > 0
将字典顺序转换为步行位
因为步行位算法是生成（反向）字典顺序排列的算法的变体，字典顺序中的每个排列都可以转换为步行位顺序中相应的排列，通过镜像适当的二进制序列的一部分。
因此，您可以使用任何算法（例如 Gosper's Hack）以字典顺序或反向字典顺序创建排列，然后转换每个排列以获得步行位顺序。
实际上，这意味着从左到右遍历二进制序列，如果您在奇数个零之后找到一个设置位，则反转序列的其余部分并从右到左遍历它，依此类推在...
代码示例 4
在下面的代码中，n,k = 7,3 的排列按字典序逆序生成，然后转换为 one-by-one：
function lexi2walk(lex) {
var seq = [], ofs = 0, pos = 0, dir = 1;
for (var i = 0; i < lex.length; ++i) {
if (seq[ofs + pos * dir] = lex[i]) {
if (pos % 2) ofs -= (dir *= -1) * (pos + lex.length - 1 - i)
else ofs += dir * (pos + 1);
pos = 0;
} else ++pos;
}
return seq;
}
function revLexi(seq) {
var max = true, pos = seq.length, set = 1;
while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
if (pos < 0) return false;
seq[pos] = 0;
while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
return true;
}
var s = [1,1,1,0,0,0,0];
document.write(s + " → " + lexi2walk(s) + "<br>");
while (revLexi(s)) document.write(s + " → " + lexi2walk(s) + "<br>");
均匀灰色路径
此算法创建的排列顺序与 D. Knuth 在 The Art of Computer Programming[=114] 中描述的 "homogeneous Gray path for combinations" 算法创建的排列顺序相似，但不完全相同=]卷。 4a，节。 7.2.1.3、式(31)&图26c.