Home>

### java - how to understand the algorithm of rearranging numbers and making combinations

I'm trying to make a program that displays all possible combinations of four numbers.
However, since I don't know, first I tried to make the number 3 fewer.

abc

is a combination of three
abc
acb
bac
bca
cab
cba
6 ways,
Since it is a combination of permutations, I think that everything is 3 × 2 × 1 = 6.

I feel like I can do it by combining recursive functions, but I couldn't come up with a way to express it in a java program.

1. What are the important points in expressing combinations with java programs?

2.I'm not good at understanding the algorithm, so if you have a good training method, please tell me.

Error message
``Error message``
Applicable source code
``Source code``
Tried

There was something similar to the program I was looking for on the net.

``````public class test {
public static void main (String [] args) {
permutation ("abcd", "");
}
public static void permutation (String q, String ans) {
// Base Case
if (q.length ()&lt;= 1) {
System.out.println (ans + q);
}
// General Case
else {
for (int i = 0;i&lt;q.length ();i ++) {
permutation (q.substring (0, i) + q.substring (i + 1),
ans + q.charAt (i));
}
}
}
}``````

The above program is
When executed, all combinations of abcd were output

``````permutation (q.substring (0, i) + q.substring (i + 1), ans + q.charAt (i));</code></pre >
<p><br />
I couldn't understand how this part works.</p>
<pre><code data-language = "Java">if (q.length ()&lt;= 1) {
System.out.println (ans + q);
}``````

I understand that it is displayed in the part of, but the process is not well understood.

Supplemental information (FW/tool version etc.)

Please provide more detailed information here.

This is true for all algorithms, but if you think about the algorithm yourself, you should try writing the data movement in order on a piece of paper, not just recursion.
If there is a sample, it is also good to try to output the progress.
If you get used to it, you can move the data in your head and drop it into the program.

The arguments q and ans of the permutation call are output below.
Increase indentation for each recursion.
(After->is the actual display.)

``````abcd,
bcd, a
cd, ab
d, abc->abcd
c, abd->abdc
bd, ac
d, acb->acbd
b, acd->acdb
acd, b
cd, ba
d, bac->bacd
a, bcd->bcda
ac, bd
c, bda->bdac
a, bdc->bdca
abd, c
bd, ca
d, cab->cabd
a, cbd->cbda
ab, cd
b, cda->cdab
a, cdb->cdba
abc, d
bc, da
c, dab->dabc
b, dac->dacb
ac, db
c, dba->dbac
a, dbc->dbca
ab, dc
b, dca->dcab
a, dcb->dcba``````

The character string without the i-th character and the ans + i-th character string are q and ans of the next permutation.

q becomes shorter and shorter with each recursion, and when it finally becomes 1 character, the concatenated with ans is output.

Since the i-th sequence is repeated, all combinations can be enumerated.

Remove one character in order from q and connect the removed character to ans. ,
Calls itself until q becomes 1 character, and when q becomes 1 character, it connects q to ans and outputs it.

That is,
First in the first loop
q ="abcd", ans =""was called as the first stage
q ="bcd", ans ="a"and the result of the recursive processing in the second stage
q ="cd", ans ="ab"in the third row
q ="d", ans ="abc" Output"abcd"and finish.
Go back to the third level
q ="cd", ans ="ab" ;, the second character is taken out, so
q ="c", ans ="abd"in the fourth row,
"abdc"is output and omitted, and the third line is processed because two characters are processed.
Go back to the second stage
・ ・ ・ ・ Repeat below.

The argument q of the permutation function is a selection candidate string. ans is the selected string.

q.substring (0, i) + q.substring (i + 1) is the character string q that connects the character string before i-th and the character string after i + 1-th, i The string without the th string.

ans + q.charAt (i) is a character string in which the i-th character string of character string q is added to the selected character string.

In other words, the i-th character is moved from the selection candidate character string q to the selected character string.

Is this familiar to you?
Original: Lexicographic permutations Problem 24
Translation: Problem 24 "Dictionary Permutation"
Reference: All combinations enumerated Java

Summary: The reference URL flow is applied to the list addition.

``````import java.util.ArrayList;
import java.util.List;
public class pe_10024 {
public static void main (String [] args) {
long start = System.nanoTime ();
func (10, 1000000);
// Correct
// 2783915460
//657.64465ms
long end = System.nanoTime ();
System.out.println ((end-start)/1000000f + "ms");
}
// sample
// 012 021
// 102 120
// 201 210
static void func (int num, int cntEnd) {
List<Integer>a = new ArrayList<Integer>();
List<Integer>b = new ArrayList<Integer>();
for (int i = 0;i<num;i ++) {
}
// a: 0-9 number
// b: empty
perm (a, b, cntEnd);
}
static void perm (List<Integer>a, List<Integer>b, int cntEnd) {
int sum = 0;
// End when a is empty
if (a.isEmpty ()) {
sum ++;
if (cntEnd == sum) {
for (int i = 0;i<b.size ();i ++) {
System.out.print (b.get (i));
}
System.out.println ();
}
}
for (int i = 0;i<a.size ();i ++) {
List<Integer>c = new ArrayList<Integer>(b);
List<Integer>d = new ArrayList<Integer>(a);
// Move numbers one by one
// d → c (a → b)