Thinking question... 2

[thelordoftherings]

Hello,

This is more a thinking question rather than pure Java question, but since I participate in this forum and I don't know where else would it go I decided to put it here.
Let's say I have an array. I need a function (even
pseudocode) that prints the whole possible combinations of it.
For example, if my Array is A B C, the output will be:
A
AB
ABC
ABCD
ABD
AC
ACD
AD
B
BC
BCD
BD
C
CD
D

Any ideas...?

Roy

 

[bledazemi]

So you are trying to get combinations of all possible lengths (without duplications). Well as first step i would say you could write a routine that would find combinations of a certain length. Then you can nest that routine into a loop and call it as many times as you need.



An inneficient way of writing such a combine routine would be to do it recursively.

Thinking recursively you would probably fall into the following pseudo-code:

function CombineFixed(CombineLength,Elements)
begin

if CombinationLength is 1 then
begin

// Simply return possible elements one by one
Combinations:=Elements;

end
otherwise
begin

// Find all possible combinations with length CombinationLength
NestedCombinations=CombineFixed(CombinationLength-1,Elements);

// From the combinations with length CombinationLength-1
// Form combinations with length CombinationLength
// This is done simply by adding
for each Combination in NestedCombinations
begin

for each Element in Elements
begin
//Dont allow duplicate elements in
if not Element in Combination then
begin
NewCombination=Element+Combination
Combinations.Add(NewCombination)
end;
end;
end;
end


return Combinations;
end;


function Combine(Elements)
begin

// Number of elements determines max length of combinations
MaxCombinationLength=Elements.NumberOfElements;

for i:=1 to MaxCombinationLength do
begin
FixedCombinations=CombineFixed(i,Elements);
Combinations.AddElements(FixedCombinations);
end;

return Combinations;
end;


The following code follows similar technique. Its slightly different from the pseudo-code above. It does all the hard work into one routine rather separated into two as the pseudo-code above describes. Surely i dont claim this code is effective by any means. Nor do i think its very user friendly but hey its a possible solution.

public class Main 
{
    public static void main(String[] args) 
    {      
        String[] combinations=combine("ABC");            
        
        for(int c=0;c<combinations.length;c++)
            System.out.println(combinations[c]);
    }
    
    private static String[] combine(String Elements)
    {
        return combine(Elements.length(),Elements);
    }
    
    ///////////////////////////////////////////////////////////////
    // function: combine 
    // purpose : Given a number of Elements (characters) form all 
    //           possible combinations of with them and return them
    //           as a string separated by carriage returns.   
    ///////////////////////////////////////////////////////////////
    private static String[] combine(int CombinationLength, String Elements)
    {
        String combinations[];
        
        if (CombinationLength==1)
        {   
           combinations=new String[Elements.length()]; 
           for(int e=0; e<Elements.length();e++)
               combinations[e]=(new String(""+Elements.charAt(e)) );
        }
        else
        {
            String NestedCombinations[]=combine(CombinationLength-1, Elements);
           
            combinations=new String[NestedCombinations.length+combineCount(Elements.length(),CombinationLength)];
            
            int c=0;
            for(int n=0; n<NestedCombinations.length; n++)
            {
                //remember the previous combinations
                combinations[c++]=NestedCombinations[n];

                for(int e=0; e<Elements.length(); e++)
                {
                    //Allow only combinations with all elements different
                    if ( 
                         (NestedCombinations[n].length()==CombinationLength-1) 
                          && 
                         (combinations[c-1].indexOf(Elements.charAt(e))==-1) 
                       )
                    {
                        combinations[c++]=new String( NestedCombinations[n]+Elements.charAt(e) );
                    }  
                }
            }
        }      
        
        return combinations;
    } 
    
      
    private static int combineCount(int nElements,int nCombinationLength)
    {
        int result=1;
        int factor=nElements;
        
        for(int e=0; e<nCombinationLength; e++)
        {
            result=result*factor;
            factor--;
        }
        
        return result;
    }
}

The way i think the code should to be is to be wrapped in a class such that one could simply call ...

Elements=new Elements("A","B","C");

Combinator combinator=new Combinator();
Combinator.AllowDuplications=false;

Elements combinations=combinator.Combine(Elements);


// Where Elements is some kind of a list that could hold anything object 
// provided they implement the Equals method which is needed to check for
// duplications

hope this will help you ...





"It is in our collective behaviour that we are most mysterious" Lewis Thomas

 

[bledazemi]

Hi Roy,

The method above (at least in the way i have coded it) will soon run out of memory. I tried 10 elements and it threw OutOfMemory exception).I am new to Java and not very familiar with the way it deals with memory and how objects are passed around in procedures. I am sure someone with experience in Java could do much better than the code above (hence more efficient). However going recursively will still eat lots of memory. Starting a new function before another one finishes fills the stack memory.


Another way would be to generate combinations for fixed maximum number of elements and then chopping off elements from the end one by one to form the new shorter combinations as they are needed. This would certainly reduce the need for memory. Certainly but not necessarily noticeably. For big numbers of elements is negligent. E.g. 10 factorial is negligable in comparison to 13 factorial.


So one starts thinking of a iterative solution.


1. As a first step
Need to realise that the problem is also solved by finding a way to swap elements of the array to form all possible unique placements of the elements (thats what combinations are so nothing new here ).



2. In attempt to find all possible unique element placements in iterative manner consider:

- Let N be the number of elements

- Start by generating N unique combinations
One way to do this is to rotate the array of elements N-1 times + 1 time the array as it is

- Take each of the N unique combinations and perform the same swap to all of them
Basically... if you decide to swap Element[1] with Element[5] in the first combination than we must do the same swap on all the other starting unique combinations. This restriction guaranties that the combinations formed after the swapping will also be unique.

The whole concept is based ont the following statement, with which i believe you will agree.



Changing all unique things in the same exact way, guaranties they will still be unique



It is important to change them all in the exact way otherwise if one or more are left untouched the changed ones could become same as those untouched.


As long as the same swap is applied to all unique combinations. The resulting combinations will remain unique in between them. Must emphasise here that this is not to say that the resulting combinations are unique compared to the all previously generated ones. Consider for example swapping elements once and then back again to as they were.

The trick is to realise (if you havent yet) that if the swap sequences are "never reversed" than the new unique combinations will be unique even when compared to the starting ones. "Never reversed" in the sense that in the end the swap sequence does not lead to an array with element positions that were found before via swapping.




"Changing all unique things in the same exact same unique ways, guaranties that they will be unique even to what they were before"



So to cut it short:

function CombineFixed(Elements)
begin
   
    N := Elements.NumberOfElements;
    
  
    StartCombinations[0]:=Elements;

    for i:=0 to N-1 do 
        StartCombinations[i]:=rotate(Elements);        
  
    
    for i:=0 to N-1 do 
    begin
        NewUniqueCombinations:=swapCombine(StartCombinations[i]);   
       
        Combinations.AddElements(NewUniqueCombinations);    
    end;
  
end;



function swapCombine(StartCombination)
begin
  
    N := StartCombinations.NumberOfElements;
 
   
    // To make sure swap sequences are never reversed 
    // first swap all Elements in combination with their
    // immediate neighbour to the right (because its the right way).
    //
    // And when all such possible immediate swaps are finished
    // do the same but this time swapping with the neigbour one 
    // after the one to the right (again because right is the right way.)
    //
    // And when all such possible immediate swaps are finished do
    // the same but this time swapping with the neigbour one after the
    // one after the one to the right (thats the right way)
    //
    // ...
    //
    // And so on until you reach and perform swapps with the neighbours
    // which are N-2 steps away to the right.

    for Distance:=1 to N-2 do 
    begin 
       // Perform all possible swaps with elements in the given distance (to the right)
       // Swaps are tried starting from the left most to element up to the one that is
       // Distance elements away from the left boundary   

       for i:=0 to N-Distance do 
       begin
         swap(SwapCombinations[i],SwapCombinations[i+distance]);
         NewCombination=SWapCombinations[i];
         Combinations.Add(NewCombination);
       end;
    end;   

    return Combinations;
  
end;

Oh well so much talk ... I could be wrong because i havent tested the above code. However two things kind of convinced me that this is a good way to find unique combinations.

1. The laws of preservation of uniqueness
Please dont take these seriously general, however i must say they were very useful due to the finite nature of the problem.

2. The swapCombine method will generate exactly

(N-1)*(N-2)*(N-3) ...*3*2 unique combinations.

And remember swapCombine is called N time (one for each starting unique combination) this means in the end the whole algorithm will generate N factorial unique combinations. And this is the maximum number of unique combinations you could get with N Elements.



Of course in order to achieve exactly what was required in the begining (combinations of all different lengths) an extra step is required. The chopping off:

function ChopOff(FixedSizeCombinations)
begin

    //GEt number of elements in one combination
    N := FixedSizeCombinations[0].NumberOfElements;
    

    for i:=0 to N-1 do
    begin
         //Get a shorter combination by getting only elements up to the i-th position 
         ShorterCombination=FixedSizeCombinations[0].SubElements(0,i);

	 VariableLengthCombinations.Add(ShorterCombination);
    end;   
   
    result:=VariableLengthCombinations;
      
end;

Hope this helps a little more ...


PS> For all that it matters the swaps could go the Left way (the one we left) which could very well be the right way.




"It is in our collective behaviour that we are most mysterious" Lewis Thomas

 

[thelordoftherings]

Dear bledazemi,

Thank you very much for all the effort you put in your answeres.
The main problem is that your solutions output for example ABC and BCA when for me they are both equal, I only need one of them...

Best regards,
Roy

 

[LFI]

This problem is actually very simple when you think about it the right way.

recursive statement: If your array is size x (greater than 1), then remove the first element, solve the problem for the other x-1 elements. Repeat every solution you've found so far, but with the xth element concatentated to it, then add the xth element by itself.

stopping condition: If your array is size 1, then the solution is the element by itself.

I have not used Vectors in a while, so consider the following to be pseudocode, but the above logic could be expressed this way:

Vector myVector = new Vector();

//start with last index
int j = myArray.length - 1;

while(j >= 0)
{
 int currSize = myVector.size();

 for(int i=0; i<currSize; i++)
 {
  myVector.add(myArray[j] + myVector.elementAt(i));
 }//end for

 myVector.add(myArray[j]);
 j--;
}//end while

This should generate the Vector elements (from your example) in the following order:

D //'D' by itself
CD //this is the above with 'C' in front
C //'C' by itself
BD //this and the next two are the above with 'B' in front
BCD
BC
B //'B' by itself
AD //this and the next six are the above with 'A' in front
ACD
AC
ABD
ABCD
ABC
AB
A //'A' by itself

At this point, j = -1, the condition of the while loop fails, and you're left with a Vector holding all your possible combinations.

'hope that helps.

Dave



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
O Time, Strength, Cash, and Patience!

 

[bledazemi]

Sorry Roy,

I missunderstood your problem ... i should have read more carefully your problem description.

Good one Dave, very nice solution.

"It is in our collective behaviour that we are most mysterious" Lewis Thomas

 

[thelordoftherings]

LFI: Thank you very much for this elegant solution.
bledazemi: don't be sorry, you put a lot of effort in your answeres and I was really impressed by that. You definitely deserve a thank you Star!