Home>

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


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.

  • Answer # 1

    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
        bc, ad
          c, adb->adbc
          b, adc->adcb
      acd, b
        cd, ba
          d, bac->bacd
          c, bad->badc
        ad, bc
          d, bca->bcad
          a, bcd->bcda
        ac, bd
          c, bda->bdac
          a, bdc->bdca
      abd, c
        bd, ca
          d, cab->cabd
          b, cad->cadb
        ad, cb
          d, cba->cbad
          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.

  • Answer # 2

    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.

  • Answer # 3

    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.

    Please think carefully.

  • Answer # 4

    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.add (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)
                c.add (d.get (i));
                d.remove (i);
                // recursion
                perm (d, c, cntEnd);
            }
        }
    }