[RUBY] 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

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:

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

Recommended Posts

Programme de recherche complète des séquences (pour la programmation du concours)
Glossaire de tous les langages de programmation
Entrée standard Python3 pour une programmation compétitive
[Programmation de compétition] [Python3] Connaissances nécessaires, pour vous-même
Une introduction à la programmation orientée objet pour les débutants par les débutants
Introduction à la programmation (Python) TA Tendency pour les débutants
[Pour les débutants] Comment étudier la programmation Mémo privé
Script pour rechercher toutes les hiérarchies d'objets sélectionnées dans Blender
Préparation au démarrage de «Python Machine Learning Programming» (pour macOS)
J'ai réfléchi à la façon d'apprendre la programmation gratuitement.
Mémos privés utilisés pour les opérations de liste et la programmation de concours
[Pour les débutants des professionnels de la compétition] Trois méthodes de saisie à retenir lors du démarrage de la programmation de compétition avec Python