順列の全探索をするプログラム（競技プログラミング向け）

順列をすべて列挙するプログラムを各言語で書きました。`10`, `20`, `30`, `40` の4つの要素があったとして次のような出力をします。要素が $ n $ 個あれば、 $ n! $ 行の出力をします。出力するところになにか処理を書けば順列の全探索ができます。

```
 10 20 30 40
 10 20 40 30
 10 30 20 40
 10 30 40 20
 10 40 20 30
 10 40 30 20
 20 10 30 40
 20 10 40 30
...
```

書いた言語：

- ライブラリ使用: C++, Scala, Ruby, Python
- 独自実装: C言語, Java, JavaScript, Elixir

経緯：

AtCoderの[ABC183 C - Travel](https://atcoder.jp/contests/abc183/tasks/abc183_c)では順列の列挙が必要でした。順列列挙のアルゴリズムがわからず、競技中は無理やり書いてACは取れたのですが、解説を読むともっとスマートなアルゴリズムがありました。しかもいくつかの言語では順列を列挙するライブラリも標準装備されていました。

悔しかったので各言語で順列を全部列挙するプログラムを書いたものです。

参考：

- [AtCoder公式の解説](https://atcoder.jp/contests/abc183/editorial/286)


# C++

C++には `next_permutation` という関数があります。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int len = 4;
  vector<int> vec(len);
  for (int i = 0; i < len; i++) vec[i] = 10 * (i+1);
  do {
    for (int i = 0; i < len; i++) cout << " " << vec[i];
    cout << endl;
  } while (next_permutation(vec.begin(), vec.end()));
}
```

# Scala

Scalaには `permutations` というメソッドがあります。

```scala
object Main extends App {
  val len = 4;
  val seq = (1 to len).map(10 * _);
  seq.permutations.foreach { seq =>
    println(" " + seq.mkString(" "));
  }
}
```

# Ruby

Rubyには `permutation` というメソッドがあります。

```ruby
len = 4
arr = (1 .. len).map do |i|
  10 * i
end
arr.permutation do |arr|
  puts(" " + arr.join(" "))
end
```

# Python

Pythonには `itertools.permutations` という関数があります。

```python
import itertools

len = 4
lst = [10 * (i+1) for i in range(len)]
for lst2 in itertools.permutations(lst):
    print(" " + " ".join(map(str, lst2)))
```

# C言語

C++の `next_permutation` を自分で実装しています。（ほとんどAtCoderの解説そのままです）

```c
#include <stdio.h>

int next_permutation(int *arr, int len) {
  int left = len - 2;
  while (left >= 0 && arr[left] >= arr[left+1]) left--;
  if (left < 0) return 0;
  int right = len - 1;
  while (arr[left] >= arr[right]) right--;
  { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
  left++;
  right = len - 1;
  while (left < right) {
    { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
    left++;
    right--;
  }
  return 1;
}

int main() {
  int len = 4;
  int arr[len];
  for (int i = 0; i < len; i++) arr[i] = 10 * (i+1);
  do {
    for (int i = 0; i < len; i++) printf(" %d", arr[i]);
    printf("\n");
  } while (next_permutation(arr, len));
}
```

# Java

C言語で実装した `next_permutation` と同じ実装です。

```java
class Main {
  public static boolean nextPermutation(int[] arr) {
    int len = arr.length;
    int left = len - 2;
    while (left >= 0 && arr[left] >= arr[left+1]) left--;
    if (left < 0) return false;
    int right = len - 1;
    while (arr[left] >= arr[right]) right--;
    { int t = arr[left]; arr[left] = arr[right];  arr[right] = t; }
    left++;
    right = len - 1;
    while (left < right) {
      { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
      left++;
      right--;
    }
    return true;
  }

  public static void main(String[] args) {
    int len = 4;
    var arr = new int[len];
    for (int i = 0; i < len; i++) {
      arr[i] = 10 * (i+1);
    }
    do {
      var sb = new StringBuilder();
      for (int i = 0; i < len; i++) {
        sb.append(String.format(" %d", arr[i]));
      }
      System.out.println(sb);
    } while (nextPermutation(arr));
  }
}
```

# JavaScript

C言語やJavaで実装した `next_permutation` と同じ実装です。

```javascript
function next_permutation(arr) {
    const len = arr.length;
    let left = len - 2;
    while (left >= 0 && arr[left] >= arr[left+1]) left--;
    if (left < 0) return false;
    let right = len - 1;
    while (arr[left] >= arr[right]) right--;
    { const t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
    left++;
    right = len - 1;
    while (left < right) {
        { const t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
        left++;
        right--;
    }
    return true;
}

const len = 4;
const arr = [];
for (let i = 0; i < len; i++) arr.push(10 * (i+1));
do {
    let str = "";
    for (let i = 0; i < len; i++) str += " " + arr[i];
    console.log(str);
} while (next_permutation(arr));
```

# Elixir

C言語やJavaでの実装とは異なるアルゴリズムです。 `next_permutation` と違って、順列の全パターンを始めに作成しています。

```elixir
defmodule Main do
  def permutations([]), do: [[]]
  def permutations(list) do
    for elem <- list, p <- permutations(list -- [elem]), do: [elem | p]
  end

  def main do
    len = 4
    list = (1 .. len) |> Enum.map(fn x -> 10 * x end)
    permutations(list) |> Enum.each(fn l ->
      IO.puts(" " <> Enum.join(l, " "))
    end)
  end
end
```