[PYTHON] Programm zur vollständigen Suche nach Sequenzen (zur Wettbewerbsprogrammierung)

Ich habe in jeder Sprache ein Programm geschrieben, das alle Sequenzen auflistet. Unter der Annahme, dass es vier Elemente gibt, "10", "20", "30" und "40", ist die Ausgabe wie folgt. Wenn $ n $ Elemente vorhanden sind, werden $ n! $ Lines ausgegeben. Wenn Sie an der auszugebenden Stelle eine Verarbeitung schreiben, können Sie die gesamte Sequenz durchsuchen.

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

Geschriebene Sprache:

• Bibliotheksnutzung: C ++, Scala, Ruby, Python
• Ursprüngliche Implementierung: C-Sprache, Java, JavaScript, Elixier

Hintergrund:

AtCoders ABC183 C --Travel erforderte eine sequentielle Aufzählung. Ich kannte den Algorithmus für die Auftragsaufzählung nicht, also schrieb ich ihn während des Wettbewerbs zwangsweise und bekam AC, aber als ich die Erklärung las, gab es einen intelligenteren Algorithmus. Darüber hinaus war in einigen Sprachen eine Bibliothek zur Aufzählung von Sequenzen ebenfalls Standardausrüstung.

Ich war enttäuscht und schrieb ein Programm, um alle Sequenzen in jeder Sprache aufzulisten.

Referenz:

• offizieller Kommentar von AtCoder

C++

C ++ hat eine Funktion namens "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 hat eine Methode namens "Permutationen".

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

Ruby

Ruby hat eine Methode namens "Permutation".

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

Python

Python hat eine Funktion namens "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)))

C Sprache

Ich implementiere die C ++ next_permutation selbst. (Fast die Erklärung von AtCoder ist die gleiche)

#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

Es ist dieselbe Implementierung wie "next_permutation", die in der Sprache C implementiert ist.

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

Es ist dieselbe Implementierung wie "next_permutation", die in C-Sprache und Java implementiert ist.

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

Es ist ein Algorithmus, der sich von der Implementierung in C-Sprache und Java unterscheidet. Im Gegensatz zu "next_permutation" werden zuerst alle Muster in der Sequenz erstellt.

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