Lucian Bumb
Lucian Bumb

Reputation: 2881

How to get all possible combinations of an integer array items?

I have an array of numbers. In this array each number is repeating for "r" times.

This function is generating the array:

    var n = 8;
var k = 4;
var r = 3;
var comb = n * r / k;

function getNumbers() {
var array = new Array();
for (i = 0; i < r; i++) {
    for (j = 0; j < n; j++) {
        array.push(j);
    }
}

return array;
}

The numbers from this array I want to split them in "comb=n*r/k" uniq small arrays with the length of k;

for this I made the following function:

function InsertNumber(array) {

var finalarray = GetArrays(comb);

for (j = 0; j < array.length; j++) {
    for (i = 0; i < finalarray.length; i++) {

        if (ContainX(array[j], finalarray[i])) {
            if (finalarray[i].length <= k) {
                finalarray[i].push(array[j]);
                Console.log(array[j]);
                var index = array.indexOf(array[j]);
                array.splice(index, 1);
                InserNumber(array);
            }
        }
    }
}
ShowTable(finalarray);
}

function GetArrays(x) {

    var array = new Array();

    for (i = 0; i < x; i++) {
        var smallArray= new Array();
        array.push(smallArray);
    }
    return array;
}

function ContainX(array,element) {
var result = false;

for (i = 0; i < array.length; i++) {
    if (element === array[i]) {
        result = true;
    } 
}
return result;
}

finaly I want to display all the small arays items in a table using this function:

function ShowTable(array) {
document.write("<table>")
for (i = 0; i < array.lenght; i++) {
    document.write("<tr>")
    for (j = 0; j < array[i].legth; j++) {
        document.write("<td>" + array[i][j] + "</td>")
    }
    document.write("</tr>")
}
document.write("</table>")
}

I think that the step by step algorithm to get the expected result may be ok, but I am not able to see the result in browser because of the recursive function InsertNumber().

Can you help me with a better method to generate all combinations of all numbers in an array, where the the array items may repeat for r times?

I am open for any solution which can fix my issue.

Edit:

Exemple: mainArray=[0,0,1,1,2,2];

I want to split this array in:

    arr1=[0,1];
    arr2=[0,2];
    arr3=[1,2];

this 3 arrays are containing all items of mainArray and are uniq!!!. 

In this exemple: n=3, k=2, r=2, comb=n*r/k=3;

    n=total unique numbers from `mainArray [0,1,2]`;
    k=length of small arrays 
    r= number of repetition of each unique n;
    comb= the number of small arrays;


**Edit2- Exemple2:**

    mainArray=[0,0,1,1,2,2,3,3,4,4]

arr1=[0,1];
arr2=[0,2];
arr3=[1,3];
arr4=[2,4];
arr5=[3,4];

n=5, unique numbers in main array;
k=2, length of small array;
r=2, repetition of each number in main array;
comb=5*2/2=number of combinations which must result!. 

(all the items from mainArray are spllited in small arr is such a way to not have small array with same items)

Upvotes: 1

Views: 485

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386550

This proposal works with an array and a given length for the part array.

Distribution of values with length = 2

0 0 1 1 2 2 3 3 4 4
0   1
  0     2
      1     3
          2     4
              3   4

Distribution of values with length = 3

0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7
0     1     2
  0     1         3
    0         2         4
          1         3         5
                2         4         6
                      3         5         7
                            4         6     7
                                  5     6     7

The key feature is to splice the used value and increase the position with length - 1 for the next item to push to the part array. If the position p is outside of the array, then the position is set to the last element of the array.

function getParts(array, length) {
    var r = [],
        values,
        i, p;
    while (array.length > length) {
        values = [];
        p = 0;
        for (i = 0; i < length; i++) {
            if (p >= array.length) {
                p = array.length - 1;
            }
            values.push(array.splice(p, 1)[0]);
            p += length - 1;
        }
        r.push(values);
    }
    r.push(array);
    return r;
}

function print(o) {
    document.write('<pre>' + JSON.stringify(o, 0, 4) + '</pre><hr>');
}

print(getParts([0, 0, 1, 1, 2, 2], 2));
print(getParts([0, 0, 1, 1, 2, 2, 3, 3, 4, 4], 2));
print(getParts([0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7], 3));

Upvotes: 1

Related Questions