[PYTHON] Programme de recherche complète des séquences (pour la programmation du concours)

J'ai écrit un programme dans chaque langue qui énumère toutes les séquences. En supposant qu'il y ait quatre éléments, «10», «20», «30» et «40», le résultat est le suivant. S'il y a des éléments $ n $, il affichera $ n! $ Lines. Si vous écrivez un traitement à l'emplacement de sortie, vous pouvez rechercher la séquence entière.

 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
...

Langue écrite:

--Utilisation de la bibliothèque: C ++, Scala, Ruby, Python

• Implémentation originale: langage C, Java, JavaScript, Elixir

Contexte:

[ABC183 C --Travel] d'AtCoder (https://atcoder.jp/contests/abc183/tasks/abc183_c) nécessitait une énumération séquentielle. Je ne connaissais pas l'algorithme d'énumération des commandes, alors je l'ai écrit de force pendant la compétition et j'ai obtenu AC, mais quand j'ai lu l'explication, il y avait un algorithme plus intelligent. De plus, dans certaines langues, une bibliothèque d'énumération des séquences était également un équipement standard.

J'ai été déçu, alors j'ai écrit un programme qui répertorie toutes les séquences dans chaque langue.

référence:

• Commentaire officiel d'AtCoder

C++

C ++ a une fonction appelée «next_permutation».

#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 a une méthode appelée «permutations».

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

Ruby

Ruby a une méthode appelée «permutation».

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

Python

Python a une fonction appelée itertools.permutations.

import itertools

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

Langage C

J'implémente moi-même le C ++ next_permutation. (Presque l'explication d'AtCoder est la même)

#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'est la même implémentation que next_permutation implémentée en langage C.

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'est la même implémentation que next_permutation implémentée en langage C et Java.

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'est un algorithme différent de l'implémentation en langage C et Java. Contrairement à «next_permutation», tous les modèles de la séquence sont créés en premier.

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