Java で配列をシフトする

配列のシフトには、異なる2つの操作があります。回転では要素を円環状に移動し、すべての要素を保持します。たとえば右に2つ回転すると、末尾の2要素が先頭に移ります。一方、先頭要素の削除では、短くなった列を返し、削除した値は失われます。配列の内容をすべて保持する必要があるなら回転を、末尾側の要素だけを処理するならスキップを選びます。

特に断りがない限り、以下の例では右回転を使います。正の距離は右回転、負の距離は左回転を表します。配列の長さを超える距離は、その長さで割った余りに正規化できます。配列の長さは固定です。新しい配列を返すコードでは、呼び出し元の元の配列を再代入または変更しない限り、その配列はそのまま保たれます。

以下の例はそれぞれ単独で実行できる Java プログラムです。ジャグリングアルゴリズムの例には出力も示しています。

回転するのか、先頭要素を削除するのかを選ぶ

int[] のようなプリミティブ配列が必要なら、ループまたは一時配列を使います。データがすでに List である場合や、参照型の配列をリストとして扱える場合は Collections.rotate() を使います。別の配列を確保せずに配列を変更したいものの、コードが複雑になることを許容できるなら、ジャグリングアルゴリズムを使います。ストリームの先頭から n 個の要素を取り除く場合は skip() を使います。これは回転ではなく、元の長さも保ちません。

ループで配列をその場で回転する

この方法では、右シフトを1回ずつ行います。末尾の値を保存してから、ほかの値を右へ移動し、保存した値をインデックス0に置きます。例では5つの整数を右へ2つ回転します。渡された配列を変更し、追加の領域は一定量だけ使用します。長さ n の配列を正規化済みの距離 k だけ回転する場合、計算量は O(n × k) です。

この例を実行します:

このセクションのコードと表示されるラベルや出力は英語のままです。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int distance = 2;
    if (values.length > 0) {
      int steps = Math.floorMod(distance, values.length);
      for (int step = 0; step < steps; step++) {
        int last = values[values.length - 1];
        for (int i = values.length - 1; i > 0; i--) {
          values[i] = values[i - 1];
        }
        values[0] = last;
      }
    }
    System.out.println(Arrays.toString(values));
  }
}

Math.floorMod は、正負の距離を0から配列の長さより1小さい値までの範囲に正規化します。長さの確認により、0での剰余演算を避け、空の配列を変更せずに済みます。正規化した距離が0の場合も配列は変わりません。この繰り返しシフトは距離が小さいときに簡単ですが、配列や距離が大きい場合は、次の2つの配列向けの方法なら各要素を1回だけ移動できます。

一時配列に回転結果を格納する

インデックスの対応関係を直接使いたく、O(n) の追加領域を確保できる場合は、2つ目の配列を作ります。右回転では、負の距離や配列より大きな距離も扱えるよう、先に距離を steps に正規化します。元のインデックスが i の要素は ((long) i + steps) % n に移動します。long 型の中間値を使うことで、有効な int 型のインデックスを加算するときのオーバーフローを防ぎます。剰余演算の前に空配列ならそのまま戻ります。

このセクションのコードと表示されるラベルや出力は英語のままです。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int distance = 2;
    int[] rotated = new int[values.length];
    if (values.length > 0) {
      int steps = Math.floorMod(distance, values.length);
      for (int i = 0; i < values.length; i++) {
        int destination = (int) (((long) i + steps) % values.length);
        rotated[destination] = values[i];
      }
    }
    System.out.println(Arrays.toString(rotated));
  }
}

移動先の式では、末尾のインデックスを超えた分が先頭に戻ります。配列の長さが有効な Java であれば、long 型の合計値は範囲内に収まり、剰余演算によって移動先は0から values.length - 1 までの値になります。配列の長さを法として同じ正規化済みの steps を加える対応は全単射なので、各要素はそれぞれ異なる位置に移り、相対的な順序も保たれます。元の配列は変更されません。元の配列を置き換える動作が必要なら、返された配列を使います。

Collections.rotate() でリストを回転する

Collections.rotate() は List を操作します。距離が正なら右へ、負なら左へ回転します。参照型の配列に Arrays.asList(array) を使うと、元の配列を参照する固定サイズのリストが作られます。要素の置き換えや回転はできますが、リストへの要素の追加や削除はできません。リストを配列に戻すと、元とは別の配列になります。int[] などのプリミティブ配列は Arrays.asList で List<Integer> にはなりません。値をボックス化するか、配列用のアルゴリズムを使ってください。

このセクションのコードと表示されるラベルや出力は英語のままです。

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    Integer[] values = {1, 2, 3, 4, 5};
    List<Integer> list = Arrays.asList(values);
    Collections.rotate(list, 2);
    Integer[] rotated = list.toArray(new Integer[0]);
    System.out.println(Arrays.toString(rotated));
  }
}

この例では、リストと values が同じ要素領域を参照しているため、回転すると配列の要素の順序も変わります。別に作成した rotated 配列にも回転後の値が入ります。オブジェクト配列やリストには簡潔な方法ですが、プリミティブ値をラッパーオブジェクトに変換するとボックス化が発生します。

ジャグリングアルゴリズムで配列をその場で回転する

ジャグリングアルゴリズムは、配列を複数の巡回に分割します。左に d 個回転する場合、各インデックスは current + d の位置から値を読み取り、配列の長さを超えた分は先頭に戻ります。オーバーフローを避けるには、コードで current >= n - d ? current - (n - d) : current + d を使って折り返し後のインデックスを計算します。d は0から n - 1 の範囲に正規化されているため、結果も0から n - 1 の範囲になります。d が0なら current のままです。独立した巡回の数は gcd(n, d) です。各巡回では、値を経路に沿って移動させ、開始位置に戻るまで続けます。追加領域 O(1) で O(n) 回の移動を行えるため、別の配列を確保したくない場合に役立ちます。

このセクションのコードと表示されるラベルや出力は英語のままです。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int rightDistance = 2;
    int n = values.length;
    if (n > 0) {
      int rightSteps = Math.floorMod(rightDistance, n);
      int leftDistance = (n - rightSteps) % n;
      int cycles = gcd(n, leftDistance);
      for (int start = 0; start < cycles; start++) {
        int saved = values[start];
        int current = start;
        while (true) {
          int next = current >= n - leftDistance
              ? current - (n - leftDistance)
              : current + leftDistance;
          if (next == start) break;
          values[current] = values[next];
          current = next;
        }
        values[current] = saved;
      }
    }
    System.out.println(Arrays.toString(values));
  }

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

[4, 5, 1, 2, 3]

コードでは、まず指定された右回転の距離を rightSteps に正規化し、次に (n - rightSteps) % n で等価な左回転の距離に変換します。要素数が5の配列では、右回転の距離 2 と -2 はそれぞれ右へ2つ、3つの回転に正規化され、対応する左回転の距離はそれぞれ3つ、2つです。Integer.MIN_VALUE も、減算の前に正規化するため安全に扱えます。左回転では、各巡回で次のインデックスから値を読み取り、配列の末尾を超えたら先頭に戻ります。コードの条件式は、合計が n - 1 を超えるときに current と leftDistance を加算しないようにします。どちらの分岐でも、加算した場合に Integer.MAX_VALUE を超えるケースを含め、結果は0から n - 1 の範囲です。巡回の数は gcd(n, leftDistance) です。正規化後の距離が0なら gcd(n, 0) は n となり、条件式は current を返すため、各値は変更されずに書き戻されます。長さの確認により、空配列では剰余演算の前に処理を終えます。ループや一時配列を使う方法のほうが保守しやすいため、追加領域を一定量に抑える必要がある場合にジャグリングを選びます。

Stream API で先頭要素をスキップする

先頭の値を末尾に回すのではなく、結果から取り除く場合は skip() を使います。残りの要素を含むストリームを返すため、そのストリームを配列に変換すると元より短い配列になり、元の配列は変更されません。スキップ数が要素数以上なら、結果は空になります。skip() に渡す数は0以上でなければなりません。呼び出し元から負の数が渡される可能性があるなら、検証するか0以上に制限してください。

このセクションのコードと表示されるラベルや出力は英語のままです。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    long count = 2;
    int[] remainder = Arrays.stream(values).skip(count).toArray();
    System.out.println(Arrays.toString(remainder));
  }
}

Arrays.stream(values) は整数ストリームを作成し、skip(count) は先頭の count 個を省き、toArray() は残りを新しいプリミティブ配列に格納します。末尾側の要素を扱うには便利ですが、結果の配列を確保します。また、すべての要素を保持する必要がある場合、回転の代わりにはなりません。