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
– GhostCat, Commented Mar 22, 2017 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
– User, Commented Mar 22, 2017 at 13:56

Tomas F. · Accepted Answer · 2017-03-22 14:44:00Z

5

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]

edited Mar 22, 2017 at 14:44

answered Mar 22, 2017 at 14:03

Tomas F.

7701 gold badge7 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

GhostCat Over a year ago

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.

Sean Patrick Floyd Over a year ago

In a code review, I'd reject this, because of the crazy and unreadable bit fiddling. I have no idea what goes on there.

Collectives™ on Stack Overflow

Finding combination of all strings in an array in Java

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related