CODEWITHSUNDEEP
javafor-looparraylistcombinations
mino
mino

Reputation: 7288

Java - Listing combinations

I'm writing a program to list all possible combinations of letters A,B,C, and D. I have successfully written a program to list all possible permutations.

However, how would I rewrite the program to work and produce all combinations (i.e.: ABCD = DCBA and AB = BA, so as long as one is there, the other need not be listed).

So far, the code for my current program is:

import java.util.ArrayList;

public class Perms {

    public static void main(String[] args) {

        ArrayList<Character> characters = new ArrayList<Character>();

        characters.add('A');
        characters.add('B');
        characters.add('C');
        characters.add('D');

        int count = 0;

        for (int i = 0; i < characters.size(); i++) {
            for (int j = 0; j < characters.size(); j++) {
                for (int k = 0; k < characters.size(); k++) {
                    for (int d = 0; d < characters.size(); d++) {
                        count++;
                        System.out.println(count + ": " + characters.get(i) + characters.get(j) + characters.get(k) + characters.get(d));
                    }
                }
            }
        }

    }
}

Upvotes: 0

Views: 3592

Answers (4)

hertzsprung
hertzsprung

Reputation: 9893

Take a look at Peter Lawrey's recursive solution, which handles combinations of a list containing repeated values.

Upvotes: 1

Suzan Cioc
Suzan Cioc

Reputation: 30097

Your second case is equivalent to the list of binary values of 4 digits. Let's assume that A is rightmost digit and D is leftmost. Then there are 16 combinations in total:

DCBA
0000
0001
0010
0011
0100
...
1110
1111

Each combination is decoded like follows:

DCBA
1010 = DB

since there are ones in B and D positions.

You have various of ways to generate and or decode binary numbers in Java.

For example, with bitwise operations:

public static void main(String[] args) {

    // starting from 1 since 0000 is not needed
    for(int i=1; i<16; ++i) {

        // bitwise operation & detects 1 in given position,
        // positions are determined by sa called "masks" 
        // mask has 1 in position you wish to extract
        // masks are 0001=1, 0010=2, 0100=4 and 1000=8
        if( (i & 1) > 0 ) System.out.print("A");
        if( (i & 2) > 0 ) System.out.print("B");
        if( (i & 4) > 0 ) System.out.print("C");
        if( (i & 8) > 0 ) System.out.print("D");

        System.out.println("");

    }
}

Upvotes: 5

Alex D
Alex D

Reputation: 30445

// Returns all combinations of a List of Characters (as Strings)
// THIS METHOD MODIFIES ITS ARGUMENT! Make sure to copy defensively if necessary
List<String> charCombinations(List<Character> chars)
{
  if(chars.isEmpty())
  {
    List<String> result = new ArrayList<String>();
    result.add("");
    return result;
  }
  else
  {
     Character    c      = chars.remove(0);
     List<String> result = charCombinations(chars);
     int          size   = result.size();
     for(int i = 0; i < size; i++)
       result.add(c + result.get(i));
     return result;
  }
}

I used List for the argument, because Set doesn't have a method to pop a single item out from the set.

Upvotes: 1

hqt
hqt

Reputation: 30266

Here is my code for your problem :)

I'm so sorry that my answer looks ugly because I just a new comer at Java. 

import java.util.Vector;

public class StackOverFlow {

    static int n ;
    static Vector<String> set;
    static int[] d ;
    public static void recursion(int t){
        if(t==n){
            PRINT();
            return;
        }
        d[t]=1;
        recursion(t+1);
        d[t]=0;
        recursion(t+1);
    }

    public static void PRINT(){
        System.out.println("ANSWER");
        for(int i=0;i<n;i++)
            if(d[i]==1) System.out.println(set.elementAt(i));
    }


    public static void main(String[] args) {                   
        n = 4;
        set = new Vector<String>(4);
        d = new int[6];
        set.add("a");
        set.add("b");
        set.add("c");
        set.add("d");
        recursion(0);
    }
}

Upvotes: 1

Related Questions