Find all combinations with repetitions but without duplicate rows

Question

There is an array of 1, 2, 3, 4. It is necessary to make all possible combinations of 3 size series, the elements can be repeated. The order of the elements in the row is not important. For instance: 114 = 411 = 141. I can't find a suitable algorithm. I have found this algorithm, but there can be no repetitions of elements, like 111 or 113, only 123,124 etc.

public void doit(){
String[] arr = {"1", "2", "3","4"};
            int count = fuctorial(arr.length);
            int max = arr.length - 1;
            System.out.println("Вариантов " + count);
            int shift = max;
            String t;
            while (count > 0) {
                t = arr[shift];
                arr[shift] = arr[shift - 1];
                arr[shift - 1] = t;
                print(arr);
                count--;
                if (shift < 2) {
                    shift = max;
                } else {
                    shift--;
                }
            }
}
    static void print(String[] arr) {
        System.out.println(Arrays.toString(arr));
    }
 
    static int fuctorial(int n) {
        return (n > 0) ? n * fuctorial(n - 1) : 1;
    }

Admin · Answer

Try this.

static void combination(int[] a, int n) {
    int size = a.length;
    int[] selected = new int[n];
    new Object() {

        void print() {
            for (int i = 0; i < n; ++i)
                System.out.print(a[selected[i]] + " ");
            System.out.println();
        }

        void combination(int index, int prev) {
            if (index >= n)
                print();
            else
                for (int i = prev; i < size; ++i)
                    combination(index + 1, selected[index] = i);
        }

    }.combination(0, 0);
}

and

int[] a = {6, 7, 8, 9};
combination(a, 3);

output:

user_6183889 · Answer

public void func() {
    boolean[] check = new boolean[49];
    for(int i=1; i <=4; i++ ) {
        for(int j=1; j <=4; j++) {
            for(int k=1; k<=4; k++) {
                int sum = i*i + j*j + k*k;
                if(!check[sum]) {
                    check[sum] = true;
                    System.out.println(i + "," + j + "," + k);
                }
            }
        }
    }
}

idea is: we take a triplet, calculate the sum of squares, and check if we already had a triplet with that sum. identical triplets will have the same sum of squares. the sum of squares will always be in the range 3-48. also, the sum is unique to each combination of numbers just like you require.

Complexity is O(N^3) where N is the size of the array. since we need combinations of 3 elements, i don't think you can go below that.

UPDATE: to make is more general, use a HashSet for the sums instead of the boolean array, and iterate 3 nested loops over the input array. calculate the sum of squares and check against the HashSet.

Performance Optimization: calculate the squares of each element in the array in advance so you dont have to calculate them over and over again.

Find all combinations with repetitions but without duplicate rows

2 Answers