Actionscript 3.0 algorithm for generating combinations from n numbers in a list

I recently had to create an application that would take a list of words in an xml document and generate a unique combination of each of those words. The spread for the set of combinations was 1 to 4. Thus for a list 1,2,3,4 the generated list had to be:
1
1,2
1,2,3
1,2,3,4
2
2,1
2,1,3
and so on...
It was one of those days when I truly wished I had stuck to my Maths. Anyroad it was back to the grindstone to find a solution for this little pickle. This is the general idea of the solution.
You begin by extraction the data from the XML and having it in an array. Next you nest 4 'for (var i:int = )' loops, for each subsequent loop the initial count parameter is set to a +1 increment of the previous loop initial count. In the first loop you add the first item in the array to the end of the array.

var c:int = 0
for (var i:int = c; i < _list.length-3; i++)
{
_displaylist.push( _list[i] )
var b:int = i +1;


The idea being that as you loop through you set up the array so that
each item in the array has a chance at being the first item in the
loop. Having set up the loop you set up a counter which increments every time the combination algorithm is run till you get to the end of the initial array. This counter sets up a recursion of the algorithm till the end of the intial list is reached. This counter sets the value for 'c'.

This is the conplete combination function:

public function combinate(c:int = 0):void
{


for (var i:int = c; i < _list.length-3; i++)
{
_displaylist.push( _list[i] )
var b:int = i +1;
for (var j:int = b; j < _list.length-2; j++)
{
_displaylist.push(_list[i] +' + '+_list[j] );
var c:int = j +1;
for (var k:int = c; k < _list.length-1; k++)
{
_displaylist.push(_list[i] +' + '+_list[j] +' + '+_list[k] );
var d:int = k +1;
for (var l:int = d; l < _list.length; l++)
{
//trace (_list[i],_list[j],_list[k],_list[l])
_displaylist.push(_list[i] +' + '+_list[j] +' + '+_list[k] +' + '+_list[l]);
}
}
}
}

if (_count < 16)
{
//trace ('count',_count, _list.length)
_list.push(_list[_count])
_count++
combinate(_count)
}else{
var m:int = Math.floor(_displaylist.length/1000);

var mlist:Array = []
for (var n:int = 0; n < m; n++)
{
mlist.push({label: (n * 1000) + ' - ' +( ((n +1)* 1000) -1), data: n * 1000});
}
_droplist = new ArrayCollection(mlist);
drop.dataProvider = _droplist;

//print()
}
}


The prototype of the application can be seen here. Ignore the 'Upload XML' that is for the final version. you will not be able to upload anything. I hope you find it useful.

3 comments:

Vengatanathan said...

Hi,

If I may revive this old thread, is there a solution to this problem.

Say that I have an array [0,1,2,3] and a parameter 2 as input

I want the output to be

0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
The parameter's length determines the number of combinations in each tuple, while the array is used to generate the numbers.

Jamie said...

Hi,

If I may revive this thread, I would really appreciate your help with this.

Say that I have an array [0,1,2,3] and a parameter 2 as input

I want the output to be

0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
The parameter's length determines the number of combinations in each tuple, while the array is used to generate the numbers.

Jamie said...

Hi,

If I may revive this thread, I would really appreciate your help with this.

Say that I have an array [0,1,2,3] and a parameter 2 as input

I want the output to be

0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
The parameter's length determines the number of combinations in each tuple, while the array is used to generate the numbers.

My Instagram