实地算法用于交织阵列
https://cs.stackexchange.com/questions/332
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
您有$ 2N $元素的数组
$$ a_1，a_2， dots，a_n，b_1，b_2， dots b_n $$
任务是使用现场算法交流数组，以使结果数组看起来像
$$ b_1，a_1，b_2，a_2， dots，b_n，a_n $$
如果没有就地要求，我们可以轻松地创建一个新的数组并复制元素，从而给出$ Mathcal {o}（n）$ time算法。
在现场要求的情况下，划分和征服算法将算法提高为$ theta（n log n）$。
所以问题是：
是否有$ Mathcal {o}（n）$ time算法，也是就位的吗？
（注意：您可以假设统一的成本单词RAM模型，因此现场转换为$ Mathcal {O}（1）$ SPACE限制）。
解决方案
这是乔（Joe）链接的论文的算法上详细阐述的答案： http://arxiv.org/abs/0805.1598
首先让我们考虑一个 $ theta（n log n）$ 使用划分和征服的算法。
1）分裂和征服
我们得到了
$$ a_1，a_2， dots，b_1，b_2， dots b_n $$
现在使用分裂和征服，有些 $ m = theta（n）$, ，我们尝试获取数组
$$ [a_1，a_2， dots，a_m，b_1，b_2，b_2， dots，b_m]，[a_ {m+1}， dots， dots，a_n，a_n，b_ {m+1}， dots b_n] $$
和反复。
注意该部分 $$ b_1，b_2， dots b_m，a_ {m+1}， dots a_n $$ 是循环移动
$$ a_ {m+1}， dots a_n，b_1， dots b_m $$
经过 $ m $ 地方。
这是一个经典 $ MATHCAL {O}（n）$ 时间。
因此，分歧和征服给了你一个 $ theta（n log n）$ 算法，具有类似的递归 $ t（n）= 2t（n/2） + theta（n）$.
2）置换周期
现在，解决该问题的另一种方法是将置换视为一组不结合周期。
置换是由（假设从 $1$)
$$ J mapsto 2J mod 2n+1 $$
如果我们以某种方式确切地知道周期是什么，使用持续的额外空间，我们可以通过选择一个元素来意识到置换 $ a $, ，确定该元素的去向（使用上述公式），将元素放在目标位置进入临时空间，放置元素 $ a $ 进入该目标位置并沿周期继续。一旦完成一个周期，我们就会进入下一个周期的一个元素，并遵循该周期等等。
这会给我们一个 $ MATHCAL {O}（n）$ 时间算法，但它假设我们“以某种方式知道确切的周期是什么”，并试图在其中进行此书籍保存 $ MATHCAL {O}（1）$ 空间限制是使这个问题困难的原因。
这是论文使用数字理论的地方。
可以证明，在情况下 $ 2N + 1 = 3^k $, ，位置的元素 $1$, $ 3，3^2， dots，3^{k-1} $ 在不同的周期中，每个周期都包含一个位置的元素 $ 3^m，m ge 0 $.
这使用了这样一个事实 $2$ 是 $（ mathbb {z}/3^k）^*$.
因此 $ 2N+1 = 3^k $, ，遵循周期方法给我们一个 $ MATHCAL {O}（n）$ 时间算法，至于每个周期，我们确切地知道从哪里开始： $3$ （包含 $1$）（可以计算这些 $ MATHCAL {O}（1）$ 空间）。
3）最终算法
现在，我们结合了上述两个：划分和征服 +置换周期。
我们做出分歧和征服，但请选择 $ m $ 以便 $ 2M+1 $ 是 $3$ 和 $ m = theta（n）$.
因此，我们仅在两个“半”上递归，我们仅在一个上循环一次，然后做 $ theta（n）$ 额外的工作。
这给了我们复发 $ t（n）= t（cn） + theta（n）$ （对于一些 $ 0 lt C lt 1 $），因此给了我们一个 $ MATHCAL {O}（n）$ 时间， $ MATHCAL {O}（1）$ 空间算法！
其他提示
我很确定我发现了一种不依赖数字理论或周期理论的算法。请注意，有一些细节需要解决（可能是明天），但我非常有信心它们会解决。我手浪是我应该睡觉的，不是因为我试图隐藏问题:)
让 A 成为第一个数组， B 第二， |A| = |B| = N 并假设 N=2^k 对于一些 k, ，为简单起见。让 A[i..j] 成为 A 与索引 i 到达 j, ， 包括的。阵列为0。让 RightmostBitPos(i) 返回最右键的（基于0）的位置，即1'的“ 1” i, ，从右边计算。该算法如下。
GetIndex(i) {
int rightPos = RightmostBitPos(i) + 1;
return i >> rightPos;
}
Interleave(A, B, N) {
if (n == 1) {
swap(a[0], b[0]);
}
else {
for (i = 0; i < N; i++)
swap(A[i], B[GetIndex(i+1)]);
for (i = 1; i <= N/2; i*=2)
Interleave(B[0..i/2-1], B[i/2..i-1], i/2);
Interleave(B[0..N/2], B[N/2+1..N], n/2);
}
}
让我们以16个数字为单位，让我们开始使用掉期交流它们，然后看看会发生什么：
1 2 3 4 5 6 7 8 | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8 | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8 | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8 | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8 | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8 | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8 | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16
特别感兴趣的是第二个数组的第一部分：
|
| 1
| 2
| 2 3
| 4 3
| 4 3 5
| 4 6 5
| 4 6 5 7
| 8 6 5 7
该模式应清楚：我们或将最低数字替换为高数字。请注意，我们始终添加一个比我们已经拥有的最高数字高的数字。如果我们能够以某种方式确切弄清楚哪个给定时间最低的数字，我们可以轻松地做到这一点。
现在，我们进行更大的示例，看看是否可以看到模式。请注意，我们不需要修复数组的大小即可构建上述示例。在某个时候，我们得到此配置（第二行从每个数字中减去16）：
16 24 20 28 18 22 26 30 17 19 21 23 25 27 29 31
0 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15
现在，这清楚地显示了一个模式：“ 1 3 5 7 9 11 13 15”全部2相距，“ 2 6 10 14”全部4分开，“ 4 12”分开8。因此，我们可以设计一种算法，该算法告诉我们下一个最小数字将是什么：机制几乎完全是二进制数字的工作方式。您在阵列的后半部分中有一点，第二季度有点等等。
因此，如果我们被允许我们足够的空间存储这些位（我们需要$ log n $位，但是我们的计算模型允许这一点 - 到数组中的指针也需要$ log n $ bit），我们可以找出哪个数字交换$ O（1）$ time摊销。
因此，我们可以将阵列的上半年以$ o（n）$时间和$ o（n）$交换的形式进入其交错状态。但是，我们确实必须修复我们的阵列的后半部分，这似乎都弄乱了（“ 8 6 5 7 13 14 15 16”）。
现在，如果我们可以“对”第二部分的上半场“排序”，我们最终以“ 5 6 7 8 13 14 15 16”结束，然后递归交织这半部分将有能力：我们将数组交织成$ O（n ）$ time（$ o（ log n）$递归调用，每个调用将输入大小减半）。请注意，我们不需要堆栈，因为这些调用是尾部递归的，因此我们的空间使用量仍然是$ o（1）$。
现在，问题是：我们需要排序的部分中是否有一些模式？尝试32个数字使我们“ 16 12 10 14 9 11 13 15”进行修复。请注意，我们这里有完全相同的模式！ “ 9 11 13 15”，“ 10 14”和“ 12”以我们之前看到的方式分组。
现在，诀窍是递归交织这些子部分。我们将“ 16”和“ 12”交织到“ 12 16”。我们将“ 12 16”和“ 10 14”交织到“ 10 12 14 16”。我们将“ 10 12 14 16”和“ 9 11 13 15”交织到“ 9 10 11 12 13 14 15 16”。这与第一部分分类。
就像上面一样，此操作的总成本为$ O（n）$。添加所有这些，我们仍然设法获得$ O（n）$的总运行时间。
一个例子：
Interleave the first half:
1 2 3 4 5 6 7 8 | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8 | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8 | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8 | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8 | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8 | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8 | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16
Sort out the first part of the second array (recursion not explicit):
8 6 5 7 13 14 15 16
6 8 5 7 13 14 15 16
5 8 6 7 13 14 15 16
5 6 8 7 13 14 15 16
5 6 7 8 13 14 15 16
Interleave again:
5 6 7 8 | 13 14 15 16
13 6 7 8 | 5 14 15 16
13 5 7 8 | 6 14 15 16
13 5 14 8 | 6 7 15 16
13 5 14 6 | 8 7 15 16
Sort out the first part of the second array:
8 7 15 16
7 8 15 16
Interleave again:
7 8 | 15 16
15 8 | 7 16
15 7 | 8 16
Interleave again:
8 16
16 8
Merge all the above:
9 1 10 2 11 3 12 4 | 13 5 14 6 | 15 7 | 16 8
这是线性时间算法中的一种非恢复性的，可在没有额外存储的阵列中交织两半的阵列。
总体想法很简单：从阵列的上半走从左到右走，将正确的值交换到位。当您前进时，尚待使用的左值将换成由正确的值腾出的空间。唯一的技巧是弄清楚如何再次将它们拉出来。
我们从大小的n阵列开始，分为2个几乎相等的一半。
[ left_items | right_items ]
当我们处理它时，它变成了
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]
交换空间随以下模式生长：a）通过删除相邻的右物品并从左侧交换新项目来增加空间； b）将最古老的物品与左侧的新项目交换。如果左项编号为1..n，则此模式看起来像
step swapspace index changed
1 A: 1 0
2 B: 2 0
3 A: 2 3 1
4 B: 4 3 0
5 A: 4 3 5 2
6 B: 4 6 5 1
7 A: 4 6 5 7 3
...
索引更改的顺序完全是 OEIS A025480, ，可以通过简单的过程计算。这允许在迄今为止添加的项目数中找到交换位置，这也是要放置的当前项目的索引。
这就是我们需要在线性时间填充序列的第一半的所有信息。
当我们到达中点时，阵列将有三个部分：[ placed_items | swapped_left_items | remaining_right_items]如果我们可以解开交换项目，我们将问题降低到一半的大小，并且可以重复。
为了解开交换空间，我们使用以下属性：由 N 交替的附加和swap_oldest操作将包含 N/2 他们年龄给出的项目 A025480(N/2)..A025480(N-1). （整数除法，较小的值较早）。
例如，如果左半部分最初持有值1..19，则交换空间将包含 [16, 12, 10, 14, 18, 11, 13, 15, 17, 19]. 。 A025480（9..18）是 [2, 5, 1, 6, 3, 7, 0, 8, 4, 9], 这正是从最旧到最新的项目的索引列表。
因此，我们可以通过前进和交换来消除交换空间 S[i] 和 S[ A(N/2 + i)]. 。这也是线性时间。
剩下的并发症是，最终您将达到正确值应处于较低索引的位置，但已经交换了。很容易找到新的位置：只需再次进行索引计算即可发现该项目交换到哪里。可能有必要遵循链条几步，直到找到一个未盘旋的位置。
在这一点上，我们合并了一半的数组，并在另一半中保持了未合并部分的顺序 N/2 + N/4 掉期。我们可以继续整个阵列的其余部分 N + N/4 + N/8 + .... 掉期严格少于 3N/2.
如何计算A025480：
这在OEI中定义为 a(2n) = n, a(2n+1) = a(n). 替代配方是a(n) = isEven(n)? n/2 : a((n-1)/2). 。这导致了使用位操作的简单算法：
index_t a025480(index_t n){
while (n&1) n=n>>1;
return n>>1;
}
这是N.的所有可能值的摊销O（1）操作。 （1/2需要1位，1/4需要2，1/8需要3，...）. 。有一个更快的方法，它使用一个小的查找表来找到最小显着的零位的位置。
鉴于这是C：
static inline index_t larger_half(index_t sz) {return sz - (sz / 2); }
static inline bool is_even(index_t i) { return ((i & 1) ^ 1); }
index_t unshuffle_item(index_t j, index_t sz)
{
index_t i = j;
do {
i = a025480(sz / 2 + i);
}
while (i < j);
return i;
}
void interleave(value_t a[], index_t n_items)
{
index_t i = 0;
index_t midpt = larger_half(n_items);
while (i < n_items - 1) {
//for out-shuffle, the left item is at an even index
if (is_even(i)) { i++; }
index_t base = i;
//emplace left half.
for (; i < midpt; i++) {
index_t j = a025480(i - base);
SWAP(a + i, a + midpt + j);
}
//unscramble swapped items
index_t swap_ct = larger_half(i - base);
for (index_t j = 0; j + 1 < swap_ct ; j++) {
index_t k = unshuffle_item(j, i - base);
if (j != k) {
SWAP(a + midpt + j, a + midpt + k);
}
}
midpt += swap_ct;
}
}
这应该是一种相当友好的算法，因为在3个数据位置中有2个被顺序访问，并且正在处理的数据量严格减少。可以从 望去 通过否定 is_even 在循环开始时测试。
