给定一个大小相等的字符串，比如说：
abcdef123456
我将如何交错两半，使相同的字符串变成这样：
a1b2c3d4e5f6
我试图尝试开发一种算法，但不能。有人会给我一些关于如何进行的提示吗？我需要这样做而不创建额外的字符串变量或数组。一两个变量就可以了。
我只是不想要一个工作代码（或算法），我需要开发一个算法并在数学上证明它的正确性。
问问题
1007 次
6 回答
6
您可以在 O(N*log(N)) 时间内完成：
Want: abcdefgh12345678 -> a1b2c3d4e5f6g7h8
a b c d e f g h
1 2 3 4 5 6 7 8
4 1-sized swaps:
a 1 c 3 e 5 g 7
b 2 d 4 f 6 h 8
a1 c3 e5 g7
b2 d4 f6 h8
2 2-sized swaps:
a1 b2 e5 f6
c3 d4 g7 h8
a1b2 e5f6
c3d4 g7h8
1 4-sized swap:
a1b2 c3d4
e5f6 g7h8
a1b2c3d4
e5f6g7h8
C中的实现：
#include <stdio.h>
#include <string.h>
void swap(void* pa, void* pb, size_t sz)
{
char *p1 = pa, *p2 = pb;
while (sz--)
{
char tmp = *p1;
*p1++ = *p2;
*p2++ = tmp;
}
}
void interleave(char* s, size_t len)
{
size_t start, step, i, j;
if (len <= 2)
return;
if (len & (len - 1))
return; // only power of 2 lengths are supported
for (start = 1, step = 2;
step < len;
start *= 2, step *= 2)
{
for (i = start, j = len / 2;
i < len / 2;
i += step, j += step)
{
swap(s + i,
s + j,
step / 2);
}
}
}
char testData[][64 + 1] =
{
{ "Aa" },
{ "ABab" },
{ "ABCDabcd" },
{ "ABCDEFGHabcdefgh" },
{ "ABCDEFGHIJKLMNOPabcdefghijklmnop" },
{ "ABCDEFGHIJKLMNOPQRSTUVWXYZ0<({[/abcdefghijklmnopqrstuvwxyz1>)}]\\" },
};
int main(void)
{
unsigned i;
for (i = 0; i < sizeof(testData) / sizeof(testData[0]); i++)
{
printf("%s -> ", testData[i]);
interleave(testData[i], strlen(testData[i]));
printf("%s\n", testData[i]);
}
return 0;
}
输出（ideone）：
Aa -> Aa
ABab -> AaBb
ABCDabcd -> AaBbCcDd
ABCDEFGHabcdefgh -> AaBbCcDdEeFfGgHh
ABCDEFGHIJKLMNOPabcdefghijklmnop -> AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPp
ABCDEFGHIJKLMNOPQRSTUVWXYZ0<({[/abcdefghijklmnopqrstuvwxyz1>)}]\ -> AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz01<>(){}[]/\
于 2013-04-14T08:08:30.920 回答
3
一般来说，这个问题是相当困难的 - 它减少到寻找排列循环。根据长度的不同，它们的数量和长度变化很大。
第一个和最后一个循环总是退化的；10 个条目数组有 2 个长度为 6 和 2 的循环，12 个条目数组有一个长度为 10 的循环。
使用一个循环可以：
for (i=j; next=get_next(i) != j; i=next) swap(i,next);
尽管 next 函数可以实现为 N 的一些相对简单的公式，但问题被推迟到对已交换的索引进行账面核算。在左侧 10 个条目的情况下，应该 [快速] 找到循环的起始位置（例如，它们是 1 和 3）。
于 2013-04-14T07:10:00.977 回答
2
好的，让我们重新开始。这是我们要做的：
def interleave(string):
i = (len(string)/2) - 1
j = i+1
while(i > 0):
k = i
while(k < j):
tmp = string[k]
string[k] = string[k+1]
string[k+1] = tmp
k+=2 #increment by 2 since were swapping every OTHER character
i-=1 #move lower bound by one
j+=1 #move upper bound by one
这是程序将要执行的操作的示例。我们将使用变量i, j, k。i并且j将分别是下限和上限，其中k将是我们交换的索引。
例子
`abcd1234`
i = 3 //got this from (length(string)/2) -1
j = 4 //this is really i+1 to begin with
k = 3 //k always starts off reset to whatever i is
swap d and 1
increment k by 2 (k = 3 + 2 = 5), since k > j we stop swapping
result `abc1d234` after the first swap
i = 3 - 1 //decrement i
j = 4 + 1 //increment j
k= 2 //reset k to i
swap c and 1, increment k (k = 2 + 2 = 4), we can swap again since k < j
swap d and 2, increment k (k = 4 + 2 = 6), k > j so we stop
//notice at EACH SWAP, the swap is occurring at index `k` and `k+1`
result `ab1c2d34`
i = 2 - 1
j = 5 + 1
k = 1
swap b and 1, increment k (k = 1 + 2 = 3), k < j so continue
swap c and 2, increment k (k = 3 + 2 = 5), k < j so continue
swap d and 3, increment k (k = 5 + 2 = 7), k > j so were done
result `a1b2c3d4`
至于证明程序的正确性，请参见此链接。它解释了如何通过循环不变量来证明这是正确的。
粗略的证明如下：
- 初始化：在循环的第一次迭代之前，我们可以看到它
i设置为(length(string)/2) - 1. 我们可以在进入循环之前看到 i <= length(string) 。 - 维护。每次迭代后，
i递减 (i = i-1, i=i-2,...) 并且必须有一个点i<length(string)。 - 终止：由于
i是正整数的递减序列，循环不变量i > 0最终将等于 false 并且循环将退出。
于 2013-04-14T06:17:48.703 回答
2
解决方案在这里是 J. Ellis 和 M. Markov。完美shuffle的原位、稳定合并。计算机杂志。43（1）：40-53，（2000）。
另请参阅此处的各种讨论：
于 2013-04-14T07:01:04.893 回答
0
好的，这是一个粗略的草图。你说你不只是想要一个算法，但你正在接受提示，所以考虑这个算法一个提示：
长度为 N。
k = N/2 - 1。
1) 从中间开始，将位置 N/2 k 处的元素移动（通过连续交换相邻的对元素）向左移动（第一次：'1' 移动到位置 1）。
2）--k。k==0吗？退出。
3) 将 N/2 处的元素移动（通过交换）（第一次：'f' 移动到位置 N-1）k 个位置到右侧。
4）--k。
编辑：上述算法是正确的，如下面的代码所示。实际上证明它是正确的已经超出了我的能力范围，虽然是一个有趣的小问题。
#include <iostream>
#include <algorithm>
int main(void)
{
std::string s("abcdefghij1234567890");
int N = s.size();
int k = N/2 - 1;
while (true)
{
for (int j=0; j<k; ++j)
{
int i = N/2 - j;
std::swap(s[i], s[i-1]);
}
--k;
if (k==0) break;
for (int j=0; j<k; ++j)
{
int i = N/2 + j;
std::swap(s[i], s[i+1]);
}
--k;
}
std::cout << s << std::endl;
return 0;
}
于 2013-04-14T07:07:36.150 回答
0
这是一个算法和工作代码。它就位，O(N)，并且在概念上很简单。
- 穿过阵列的前半部分，将项目交换到位。
- 从左半部分开始的项目将在我们需要它们之前被交换到右边，所以我们使用一个技巧来确定它们被交换到的位置。
- 当我们到达中点时，整理被交换到右侧的未放置的左侧项目。
- 使用相同技巧的变体来找到正确的解扰顺序。
- 对剩余的半阵列重复此操作。
这会通过阵列进行不超过 N+N/2 次交换，并且不需要临时存储。
诀窍是找到交换项目的索引。左边的项目在放置时被交换到由右边的项目腾出的交换空间中。交换空间按以下顺序增长：
- 将一个项目添加到末尾（进入由右项目腾出的空间）
- 将一个项目与最旧的现有（左）项目交换。
按顺序添加项目 1..N 给出：
1 2 23 43 435 465 4657 ...
每一步更改的索引为：
0 0 1 0 2 1 3 ...
这个序列正好是OEIS A025480，并且可以在 O(1) 摊销时间内计算：
def next_index(n):
while n&1: n=n>>1
return n>>1
一旦我们在交换 N 个项目后到达中点，我们就需要解读。交换空间将包含 N/2 个项目，其中应位于偏移量的项目的实际索引由i给出next_index(N/2+i)。我们可以通过交换空间前进，将物品放回原处。唯一的复杂之处在于，随着我们的前进，我们最终可能会找到一个位于目标索引左侧的源索引，因此已经在其他地方进行了交换。但是我们可以通过再次查找之前的索引来找出它在哪里。
def unscramble(start,i):
j = next_index(start+i)
while j<i: j = next_index(start+j)
return j
请注意，这只是索引计算，而不是数据移动。在实践中，所有 N 的调用总数next_index< 3N。
这就是完整实现所需的全部内容：
def interleave(a, idx=0):
if (len(a)<2): return
midpt = len(a)//2
# the following line makes this an out-shuffle.
# add a `not` to make an in-shuffle
base = 1 if idx&1==0 else 0
for i in range(base,midpt):
j=next_index(i-base)
swap(a,i,midpt+j)
for i in range(larger_half(midpt)-1):
j = unscramble( (midpt-base)//2, i);
if (i!=j):
swap(a, midpt+i, midpt+j)
interleave(a[midpt:], idx+midpt)
最后的尾递归可以很容易地被循环替换。Python 的数组语法就不那么优雅了。另请注意，对于此递归版本，输入必须是 numpy 数组而不是 python 列表，因为标准列表切片会创建不传播备份的索引副本。
这是验证正确性的快速测试。（一副 52 张牌的 8 次完美洗牌将其恢复到原始顺序）。
A = numpy.arange(52)
B = A.copy()
C =numpy.empty(52)
for _ in range(8):
#manual interleave
C[0::2]=numpy.array(A[:26])
C[1::2]=numpy.array(A[26:])
#our interleave
interleave(A)
print(A)
assert(numpy.array_equal(A,C))
assert(numpy.array_equal(A, B))
于 2019-03-09T01:38:06.410 回答