Introduction to algorithms in java-lexicographic order / combination omnivorous (part1)

Article summary

This is a series of articles that I have compiled in my study and memo. The seventh bullet. Click here for previous articles.

In this article

--Lexicographic order / combination, etc.

I will study about. Lexicographic orders and combinations often appear, so let's take this opportunity to master them. It seems that it is sometimes called a permutation full search.

Mathematical lexicographic order, permutation, and combination explanations are ~~ troublesome ~~ I already understand them, so let's omit them.

This time, I will think about various things while solving the problem. I will search for past questions and solve problems like that.

example

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

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

There was such a problem. The problem is lexicographic order. It's a C problem, and there aren't many restrictions, so if you simply go it, you might not be able to solve it without thinking about it, but let's think about it.

Let's take a look at one input example and output example.

Input example
3 1 3 2 3 1 2

Output example
3

If you read something like a commentary,

Permutations of size 3(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)There are 6 of them. this house(1, 3, 2)Is second in lexicographical order,(3, 1, 2)Is the fifth in lexicographical order, so the answer is|2−5|=It is 3.

Was written. It would be nice if the size (number) in the permutation could be found. In the c ++ language, there is a function like next_permutation, but in java there is no such thing as the next element of the permutation, so it's a bit confusing to implement. In such a case, I will refer to the answer without hesitation. Please wait for a while as I will refer to the explanation and other people's answer examples. ..

... Damn it. .. .. It seems that all C ++ people are doing next_permutation. By the way, it seems that permutations can be listed even in DFS, so I thought it would be okay to try it once after studying DFS. I managed to find the link here. The link attached to the link destination seems to be the original one, but it seems that java handles all the elements of the permutation in the list. Let's use this.

Link quote

    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));
            }
        }
    }

It may be a little difficult to understand, but if you put the first character string in the permutation, it will be output in the lexicographic order of that character string.

permutation("abc",""); When you execute abc acb bac bca cab cba

Was displayed. It's amazing. I will use this to solve this problem.

[Answer example]

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);

		//word count
		int n = sc.nextInt();

		//Variable to store a list of permutations
		list = new ArrayList<>();

		// p,Receive input of q
		String p = "";
		String q = "";
		String[] p_sort = new String[n]; //I want to store the first element of a permutation
		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_Made sort the first element of a permutation
		String p_sort_str = "";
		for (String p_sort_tmp : p_sort) {
			p_sort_str += p_sort_tmp;
		}

		//Fill the list with values
		permutation(p_sort_str, "");

		//Output the absolute value of index
		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));
			}
		}
	}
}

Could you write it relatively simply? It's amazing that permutations can be calculated like this.

It seems that it can be applied, so let's use it to solve many other problems. It would be nice to have a class or library like c ++ or python. ..

I want to solve other problems, so this article is part 1, so let's solve other lexicographic order and combination problems.

See you next time!