Einführung in Algorithmen mit Java-Dictionary Reihenfolge / Kombination verschiedener Lebensmittel (Teil1)

Artikelübersicht

Dies ist eine Reihe von Artikeln, die ich in meiner Studie und meinem Memo zusammengestellt habe. Die siebte Kugel. Klicken Sie hier für vorherige Artikel.

In diesem Artikel

• Wörterbuchreihenfolge / -kombination usw.

Ich werde darüber lernen. Wörterbücher und Kombinationen werden häufig angezeigt. Lassen Sie uns diese Gelegenheit nutzen, um sie zu beherrschen. Es scheint, dass es manchmal eine sequentielle vollständige Suche genannt wird.

Ich verstehe bereits die Reihenfolge des mathematischen Wörterbuchs, die Permutation und die Erklärung der Kombination ~~ es ist ärgerlich ~~, also lassen wir es weg.

Dieses Mal werde ich über verschiedene Dinge nachdenken, während ich das Problem löse. Ich werde nach früheren Fragen suchen und solche Probleme lösen.

Beispiel

Beispiel: AtCoder --abc150-c "Count Order"

N
P1 P2 ... PN
Q1 Q2 ... QN

Es gab so ein Problem. Das ・ Es ist ein Problem wie Wörterbuchreihenfolge. Es ist ein C-Problem, und es gibt nicht viele Einschränkungen. Wenn Sie es also einfach angehen, können Sie es möglicherweise nicht lösen, ohne darüber nachzudenken, aber lassen Sie uns darüber nachdenken.

Schauen wir uns ein Eingabe- und Ausgabebeispiel an.

Eingabebeispiel
3 1 3 2 3 1 2

Ausgabebeispiel
3

Wenn Sie so etwas wie einen Kommentar lesen,

Die Reihenfolge der Größe 3 ist(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)Es gibt 6 von ihnen. dieses Haus(1, 3, 2)Ist an zweiter Stelle in lexikalischer Reihenfolge,(3, 1, 2)Ist der fünfte in lexikalischer Reihenfolge, so lautet die Antwort|2−5|=Es ist 3.

Wurde geschrieben. Es wäre schön, wenn die Größe (Anzahl) in der Bestellung erforderlich wäre. In der c ++ - Sprache gibt es eine Funktion wie next_permutation, aber in Java gibt es kein nächstes Element der Sequenz, daher ist die Implementierung etwas verwirrend. In einem solchen Fall werde ich ohne zu zögern auf die Antwort verweisen. Bitte warten Sie eine Weile, da ich mich auf die Erklärung und die Antwortbeispiele anderer beziehen werde. ..

... Verdammt. .. .. Es scheint, dass alle C ++ - Spieler next_permutation ausführen. Übrigens scheint es, dass sogar DFS die Reihenfolge aufzählen kann, also dachte ich, es wäre in Ordnung, es einmal nach dem Studium von DFS zu versuchen. Ich habe den Link [hier] gefunden (https://qiita.com/masakinpo/items/b6ae147d9a61b592240a). Der am Linkziel eingefügte Link scheint der ursprüngliche zu sein, aber Java behandelt anscheinend alle Elemente der Sequenz in der Liste. Lassen Sie uns dies verwenden.

Verknüpftes Zitat

    public static void permutation(String q, String ans){
        // Base Case
        if(q.length() <= 1) {
            System.out.println(ans + q);
        }
        // General Case
        else {
            for (int i = 0; i < q.length(); i++) {
                permutation(q.substring(0, i) + q.substring(i + 1),
                        ans + q.charAt(i));
            }
        }
    }

Es mag etwas schwierig zu verstehen sein, aber es scheint, dass wenn Sie die erste Zeichenfolge in der Sequenz eingeben, diese in der lexikalischen Reihenfolge dieser Zeichenfolge ausgegeben wird.

permutation("abc",""); Wenn Sie ausführen abc acb bac bca cab cba

Wurde angezeigt. Es ist wunderbar. Ich werde dies verwenden, um dieses Problem zu lösen.

[Antwortbeispiel]

Main.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static ArrayList<String> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		//Wortzahl
		int n = sc.nextInt();

		//Eine Variable, die eine Liste von Sequenzen speichert
		list = new ArrayList<>();

		// p,Empfangen Sie die Eingabe von q
		String p = "";
		String q = "";
		String[] p_sort = new String[n]; //Ich möchte das erste Element einer Sequenz speichern
		for (int i = 0; i < n; i++) {
			String tmp = sc.next();
			p += tmp;
			p_sort[i] = tmp;
		}
		for (int i = 0; i < n; i++) {
			q += sc.next();
		}

		Arrays.parallelSort(p_sort); // p_machte sort das erste Element der Sequenz
		String p_sort_str = "";
		for (String p_sort_tmp : p_sort) {
			p_sort_str += p_sort_tmp;
		}

		//Füllen Sie die Liste mit Werten
		permutation(p_sort_str, "");

		//Absolutwert des Index ausgeben
		System.out.println(Math.abs(list.indexOf(q) - list.indexOf(p)));
	}

	public static void permutation(String q, String ans) {
		// Base Case
		if (q.length() <= 1) {
			list.add(ans + q);
		}
		// General Case
		else {
			for (int i = 0; i < q.length(); i++) {
				permutation(q.substring(0, i) + q.substring(i + 1),
						ans + q.charAt(i));
			}
		}
	}
}

Könnten Sie es relativ einfach schreiben? Es ist erstaunlich, die Reihenfolge der Bestellungen so berechnen zu können.

Es scheint, dass es angewendet werden kann, also lassen Sie uns es verwenden, um viele andere Probleme zu lösen. Es wäre schön, eine Klasse oder Bibliothek wie C ++ oder Python zu haben. ..

Ich möchte andere Probleme lösen, daher ist dieser Artikel Teil 1, also lassen Sie uns andere Wörterbuchreihenfolge- und Kombinationsprobleme lösen.

Bis zum nächsten Mal!