Finding combination of all strings in an array in Java

Question

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.

Why should b,c come before a,c? Or a,b? I have no idea with "keeping initial order". Or is it just about: it should be a,c and not c,a? — GhostCat, Mar 22 '17 at 13:51
Yes the it should be a,b and not b,a. The order of subsets does not matter, but the order of elements inside the subset is. — User, Mar 22 '17 at 13:56

Tomas F. · Accepted Answer · 2017-03-22T14:44:00.453

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]

Where: to make your answer really helpful to others, you probably want to explain that fancy if condition you are using ... you see, those code only answers are "kind of ok", but not really. If you want to convince people to upvote (and not downvote) ... consider adding some explanations. — GhostCat, Mar 22 '17 at 14:14
In a code review, I'd reject this, because of the crazy and unreadable bit fiddling. I have no idea what goes on there. — Sean Patrick Floyd, Mar 22 '17 at 14:16

Finding combination of all strings in an array in Java

1 Answers1