在java的n个位置数组的循环左移 [英] circular left shift of an array by n positions in java

问题描述

我试图做的只使用一个单一的一维数组n个位置数组的循环左移。我能做到这两个数组，但我还没有想出如何使用一个做到这一点。请给您的建议

I am trying to do the circular left shift of an array by n positions using only a single 1D array. I can do it in two arrays, but I haven't figured out how to do it using one. Please give your suggestions

推荐答案

有实际上是一个聪明的算法的。我们将使用 A 来表示数组， N 来表示数组大小，和 ñ来表示位置数移位。后移，你希望第i 元素移动到（（I + N）型N）个的位置，因此，我们可以通过下面的映射定义新的位置：

There is actually a clever algorithm for that. We'll use A to denote the array, N to denote the array size, and n to denote the number of positions to shift. After the shift you would like the i-th element to move to the ((i + n) mode N)-th position, Hence we can define the new positions by the following mapping:

f(j) := (j + n) mod N  (j = 0,...,N - 1)

这个算法背后的总体思路是这样的：我们不希望各地更多的则需要移动元素，因此理想情况下，我们想简单地将每个元素在它的正确的（转移）在第一次尝试的位置。假设我们在位置开始元素 I 。我们想要做的是在位置 I 来位置 F（I）移动元素，但然后我们会覆盖元素在那个位置，所以我们需要先保存在位置元素F（I），然后执行的转变。一旦我们转向的第一要素，我们需要选择另一个元素转移。由于我们要节省空间，明显的候选人就是我们刚才保存的元素（即在位置 F（我的元素））。像以前一样，我们在保存位置的元素 F（F（I））然后我们保存的元素复制到该位置。我们一直在重复这个过程（通过位置会 I，F（I），F（F（I）），F（F（F（I））），... ），直到我们达到我们已经移位的元件（我们正在gauranteed做的，因为有finitly许多位置）。如果我们通过所有的元素通过，那么我们都做了，如果没有的话，我们选择另一个要素（即尚未转移），说在位置Ĵ，和重复上述步骤（通过Ĵ中，f（J去），F（F（J）），F（F（F（J））），... ）。而已。但在此之前，我们可以实现这样的算法，甚至之前，我们决定这是否确实是一个不错的算法，我们需要回答几个问题：

The general idea behind this algorithm goes like this: We don't want to move elements around more then necessary, so ideally we would like to simply place each element in it's proper (shifted) position on the first try. Say we start with the element at position i. What we want to do is move the element at position i to position f(i), but then we'll overwrite the element at that position, so we need to first save the element at position f(i) and then perform the shift. Once we shifted the first element, we need to pick another element to shift. Since we want to conserve space, the obvious candidate is the element we just saved (the element that was in position f(i)). Like before, we save the element at position f(f(i)) and then copy our saved element into that position. We keep repeating this process (going through positions i, f(i), f(f(i)), f(f(f(i))), ...) until we reach an element we already shifted (which we are gauranteed to do, since there are finitly many position). If we passed through all of the elements, then we are done, if not then we select another element (that hasn't been shifted yet), say at position j, and repeat the procedure (going through j, f(j), f(f(j)), f(f(f(j))), ...). That's it. But before we can implement such an algorithm, or even before we decide whether this is indeed a good algorithm we need to answer a few questions:

1. 假设我们通过位置 I，F（I），F（F（I）），... 迭代。我们怎么能告诉我们达成已移的位置？我们需要保存我们穿过每一个位置？如果我们这样做，那么这意味着我们需要持有大小N（覆盖所有位置）的数组，我们还需要执行查找每次我们转移元素的时间。这将使算法非常innefficient。幸运的是这时并不需要，因为序列 I，F（I），F（F（I）），... 必须在位置<$ C $本身绕到C> I ，所以我们只需要等待，直到我们到达那个位置。我们可以按如下证明这assetion：假设我们遇到的第一个重复的元素不是 I 。然后，我们必须有2个不同的元素，当转移将达到同样的位置 - 一个矛盾

1. Say we iterate through positions i, f(i), f(f(i)), .... How can we tell that we reached a position that has already been shifted? Do we need to save every position we passed through? If we do, then this means we need to hold an array of size N (to cover all positions), and we also need to perform a lookup every time we shift an element. this would make the algorithm terribly innefficient. Luckily this is not neccessary, since the sequence i, f(i), f(f(i)), ... must wrap around itself at position i, so we only need to wait until we reach that position. We can prove this assetion as follows: Assume that the first repeated element we meet is not i. Then we must have 2 different elements, that when shifted will reach the same position - a contradiction.

说我们吃完经历 I，F（I），F（F（I）），... ，但仍然有保持元素未移位（我们可以通过计算告诉我们有多少个元素转移）。我们现在怎么办找到一个位置Ĵ包含这样的元素？而且，一旦我们完成了这第二次迭代（通过Ĵ中，f（J），F（F（J）），... 去），我们如何找到第三位置 K 与不移位的元素？等等。这也可能表明，我们需要保存一个数组占二手旧\\未使用的元素，并借此在查找每次我们需要找到一个未使用的元素。但是，我们可以再次放松，因为，正如我们很快就会显示，所有的起始位置的（我们记为 I ，<$的C $ C>Ĵ和 K ）相邻。这意味着，如果我们从位置 I 开始，我们接下来将选择 I + 1 ，然后 I + 2 ，等等...

Say we finished going through i, f(i), f(f(i)), ..., but there are still elements that remain unshifted (we can tell by counting how many elements we shifted). How do we now find a position j that contains such an element? And also, once we finished this second iteration (going through j, f(j), f(f(j)), ...) how do we find a third position k with an unshifted element? and so on.. This too might suggest we need to save an array to account for used used\unused elements, and perfrom a lookup everytime we need to find an unused element. However, we can again relax, since, as we'll soon show, all of the starting positions (which we denoted by i, j and k) are adjacent. which means, that if we start from position i, we'll next select i + 1, and then i + 2, and so on...

可能的序列 I，F（I），F（F（I）），... 和Ĵ，女（J），F（F（J）），... （其中 I 和Ĵ是不同的）含有共同的元素？如果他们这样做，这将意味着该算法是没用的，因为它可以在同一元素两次转变 - 导致它在错误的位置结束。然后（当然）答案是，他们不能包含常见的元素。我们将说明为什么。

might the sequences i, f(i), f(f(i)), ... and j, f(j), f(f(j)), ... (wherei and j are different) contain common elements? If they do this would mean that the algorithm is useless, since it could shift the same element twice - causing it to end up in the wrong position. The answer then (of course), is that they cannot contain common elements. And we will show why.

让我们表示 D：= GCD（N，N）。对于整数中的每一个： I = 0，...，D - 1 我们定义了以下一组：

Let us denoted := gcd(N, n). For every one of the integers: i = 0,...,d - 1 we define the following set:

S(i) := { kd + i | k = 0,...,N/d - 1}

这是很容易看到，集 S（0），...，S（D - 1）一起覆盖集 { 0，...，N - 1} 。我们还注意到，在一组划分元素时 S（I）按 D ，我们剩下的余数 I ，除以一个元素，从一组不同的 S（j）条按 D 将离开我们用不同的余数（Ĵ）。因此，没有任何两个集包含一个共同的元件。有了这个，我们已经建立了集 S（0），...，S（D - 1）形成 0分区{,. ..，N - 1}

It is easy to see that the sets S(0),...,S(d - 1) together cover the set {0,...,N - 1}. We also observe that when dividing an element in a set S(i) by d, we are left with remainder i, and dividing an element from a different set S(j) by d will leave us with a different remainder (j). Thus, no two sets contain a common element. With this we have established that the sets S(0),...,S(d - 1) form a partition of {0,...,N - 1}

现在，每 I = 0，...，D - 1 ，我们将定义集 T（I）为 I，F（I），F（F（I）），... 。通过 F的的定义，我们可以写 T（I）如下：

Now, for every i = 0,...,d - 1, we will define the set T(i) as i, f(i), f(f(i)), .... By the definition of f we can write T(i) as follows:

T(i) = {(kn + i) mod N | k is an integer}

我们观察，如果 X 是 T（I），那么我们可以对一些写<元素code> K ：

We observe that if x is an element in T(i), then we can write for some k:

x = (kn + i) mod N = (k(n/d)d + i) mod N

让我们表示 Z：= K（N / D）模N / D ，然后通过 D ，我们有：

kn mod N = zd

因此​​：

x = (kn + i) mod N = zd + i

因此​​， X 也在 S（I）。相若，如果我们采取一些是从 S（I）我们观察到，在某些 K ：

Thus, x is also in S(i). Similarily, If we take some y from S(i) we observe that for some k:

y = kd + i

由于 GCD（N / D，N / D）= 1 存在一个①这样 q（N / D）模N / D = 1 （一模逆），因此，我们可以写（由 KD ）：

Since gcd(n/d, N/d) = 1 there exists a q such that q(n/d) mod N/d = 1 (a modular inverse), thus we can write (multiplying by kd):

kd = kqn mod N

因此​​：

y = kd + i = ((kq)n + i) mod N

因此​​，是也在 T（I）。我们的结论是 T（I）= S（I）。从这个事实我们可以很容易地展示我们的previous assetions。首先，由于集合形成的分区{0，...，N - 1} 第三断言（没有两个序列包含一个共同的元素）成立。其次，通过集合的定义 S（I）我们可以采取任何一组 D 相邻元素的 {0，...，N - 1} 和他们每个人将被放置在一组不同的。这满足了第二个说法。

Thus, y is also in T(i). We conclude that T(i) = S(i). From this fact we can easily show our previous assetions. First off, since the sets form a partition of {0,...,N - 1} the third assertion (no two sequences contain a common element) is satisfied. Second, by the definition of the sets S(i) we can take any group of d adjacent elements in {0,...N - 1} and each of them will be placed in a different set. This satisfies the second assertion.

这意味着是，我们可以旋转位置的所有元素 0，D，2D，...，（N / D - 1）D 通过简单地在位置替换元素ñ模N 在位置 0 元素，在位置的元素 2N N模与位置的元素ñ模N ，等等..直到我们回到了元素位置 0 （我们放心会发生）。这里是一个伪code例如：

What this means is that we can rotate all elements in positions 0, d, 2d, ..., (N/d - 1)d by simply replacing the element at position n mod N with the element at position 0, the element at position 2n mod N with the element at position n mod N, and so on.. until we return to the element in position 0 (which we are assured will happen). Here is a pseudo-code example:

temp <- A[0]
j <- N - (n mod N)
while j != 0 do
    A[(j + n) mod N] <- A[j];
    j <- (j - n) mod N
A[n mod N] <- temp;

这涵盖整个集合 S（0）。为了弥补套，其余即 S（1），...，S（D-1），我们将简单地在每个迭代设置我们也以同样的方式第一个：

This covers the entire set S(0). To cover the rest of the sets, Namely S(1), ... ,S(d-1), we will simply iterate over each set the same way we did for the first:

for i <- 0 to d - 1
    temp <- A[i]
    j <- N - ((n - i) mod N)
    while j != i do
        A[(j + n) mod N] <- A[j];
        j <- (j - n) mod N
    A[(i + n) mod N] <- temp;

请注意，虽然我们有两个嵌套循环，每个元素都被精确地移动一次，我们使用 O（1）的空间。实现的Java中的〔实施例：

Note that while we have two nested loops, each element is moved exactly once, and we use O(1) space. An exmaple of an implementation in Java:

public static int gcd(int a, int b) {
    while(b != 0) {
        int c = a;
        a = b;
        b = c % a;
    }
    return a;
}

public static void shift_array(int[] A, int n) {
    int N = A.length;
    n %= N;
    if(n < 0)
        n = N + n;
    int d = gcd(N, n);
    for(int i = 0; i < d; i++) {
        int temp = A[i];
        for(int j = i - n + N; j != i; j = (j - n + N) % N)
            A[(j + n) % N] = A[j];
        A[i + n] = temp;
    }
}

这篇关于在java的n个位置数组的循环左移的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！