[Java] Introduction to algorithms in java-lexicographical order/combined omnivorous (part1)

4 minute read

Article summary

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

# Articles
6 Introduction to Algorithms in java-Squatting method
5 Introduction to Algorithms in Java-Cumulative Sum
4 Introduction to algorithms with java-Search (bit full search)
3 Introduction to Algorithms in Java-Search (Breadth-first search)
2 Introduction to algorithms with java-Search (depth-first search)
1 Introduction to Algorithms in Java-Search (Full Search, Binary Search)

In this article

  • Lexical order/combination etc.

Study about Since lexicographical orders and combinations often appear, let’s master this opportunity. It seems that it is also called permutation full search.

I will understand the mathematical lexicographical order, permutation, and the explanation of combination ~~ troublesome ~ ~ I will omit it, so let’s omit it.

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


Example: AtCoder-abc150-c “Count Order”

Click here for question texts/input examples, etc.
*Please refer to the problem link as much as possible
- -- (Start of section) 【Problem statement】 There are permutations of size N (a sequence of (1, 2, ..., N) permuted) P, Q. There are N! possible permutations of size N. Find |a−b|, where P is the lexicographically the ath smallest and Q is the lexicographically the bth smallest. [Note] For two sequences X, Y, X is defined to be lexicographically less than Y when some integer k exists and Xi=Yi (1 ≤ i<k) and Xk<Yk. [Restrictions] - 2 ≤ N ≤ 8 - P and Q are permutations of size N. - All inputs are integers. 【input】 Input is given from standard input in the following format: ``` N P1 P2 ... PN Q1 Q2 ... QN ``` 【output】 Print |a−b|. (End of section) - --

I had such a problem. The question is lexicographical order. Since it is a C problem and there are not so many restrictions, it seems that it may be possible to solve it without thinking carefully if it goes simply, but let’s think about it for a moment.

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

3 1 3 2 3 1 2

3 If you read something like a commentary, > A permutation of size 3 is (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3 , 2, 1). Of these, (1, 3, 2) is lexicographically second and (3, 1, 2) lexicographically fifth, so the answer is |2−5|=3. It was written. It would be nice if the size (order) in the permutation is required. In the C++ language, there are functions such as next_permutation, but in Java there is no such thing as the next element of the permutation, so I'm a bit confused about the implementation. In such a case, I will refer to the answer without hesitation. I will refer to the explanation and other people's answers, so please wait a little. .. ...Dude. .. .. It seems that everyone in C++ is doing next_permutation. By the way, I can enumerate the permutations even with DFS, so I thought it would be nice to try it once when studying DFS. I managed to find the link [here](https://qiita.com/masakinpo/items/b6ae147d9a61b592240a). It seems that the link pasted to the link destination is the original one, but it seems that the process of putting all the elements of the permutation into the list is done by java. Let's use this. #### **` link quote`** ``` java 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 confusing, but it seems that if you insert the first character string of the permutation, it will output in lexicographical order of that character string. `permutation("abc","");` When I run `abc` `acb` `bac` `bca` `cab` `cba` And displayed it. It's amazing. I will use this to solve this problem. [Answer example] #### **`Main.java`** ``` java import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static ArrayList list; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // word count int n = sc.nextInt(); // A variable that stores a list of permutations list = new ArrayList<>(); // receive p,q input String p = ""; String q = ""; String[] p_sort = new String[n]; // want to store the first element of the 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); // made p_sort the first element of the 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)); } } } } ``` Is it relatively simple to write? It's amazing that you can calculate permutations like this. It can be applied, so let's solve a lot of other problems. It would be nice to have classes such as c++ or python, or a library. .. I want to solve other problems, so this article is part1, so let's solve other lexicographical order and combination problems. See you next time!