CODEWITHSUNDEEP
javaarrayscombinations
User
User

Reputation: 79

Finding combination of all strings in an array in Java

I am trying to find combinations of strings in an array {"A","B","C"} without repetition and order of elements should be preserved in subset. Desired order is [["B","C"], ["A","C"], ["A","B"], ["A","B","C"], ["A"], ["C"], ["B"]]. I have tried writing logic using the answers found in this question, and found that order of elements are not preserved.

public static Set <JSONArray> getCombinations( int k , JSONArray properties )
        {
            Set <JSONArray> combinations = new LinkedHashSet <JSONArray>();
            try
                {
                    if ( k == 0 )
                        {
                            combinations.add( new JSONArray() );
                            return combinations;
                        }
                    for ( int i = 0 ; i < properties.length() ; i++ )
                        {
                            String element = properties.getString( i );
                            JSONArray sublist = getSublist( properties , i + 1 );
                            combinations.add( sublist );
                            Set <JSONArray> combinations2 = getCombinations( k - 1 , sublist );
                            for ( JSONArray previous : combinations2 )
                                {

                                    previous.put( element );
                                    combinations.add( previous );
                                }
                        }
                }
            catch ( Exception e )
                {
                    System.out.println( "Exception :: " + e );
                }
            return combinations;
        }

    public static JSONArray getSublist( JSONArray list , int i ) throws JSONException
        {
            JSONArray sublist = new JSONArray();
            for ( int j = i ; j < list.length() ; j++ )
                {
                    sublist.put( list.getString( j ) );
                }
            return reverseArray( sublist );
        }

Output is :: [["B","C"], ["C","A"], ["B","A"], ["C","B","A"], ["A"], ["C"], ["B"]]. But i need the order to be preserved like ["C","A"] should be ["A","C"]. Any thoughts would be helpful.

PS: The order of subsets does not matter, but the order of elements inside the subset is.

Upvotes: 2

Views: 2246

Answers (1)

Tomas F.
Tomas F.

Reputation: 720

Combination can be represented by a number - in binary form, number at each position tells whether the element will be present or not. E.g. 5=101 -> {A, C}

So, lets iterate over combinations = numbers in range <0..2^n-1> and get elements corresponding to the number, it means those which index is present in binary representation of combination. 

 public class Combins {

            static String[] a = new String[] { "A", "B", "C" };

            public static void main(final String[] args) {

                final int maxbit = 1 << a.length;

                //for each combination given by a (binary) number 'p'...
                for (int p = 0; p < maxbit; p++) {
                    final List<String> res = new ArrayList<String>();

                    //evaluate if array 'a' element at index 'i' is present in combination (and include it if so)
                    for (int i = 0; i < a.length; i++) {
                        if ((1 << i & p) > 0) {
                            res.add(a[i]);
                        }
                    }
                    System.out.println(Arrays.toString(res.toArray()));
                }
            }
        }

Output is:

[]
[A]
[B]
[A, B]
[C]
[A, C]
[B, C]
[A, B, C]

Upvotes: 5

Related Questions