Найдите все комбинации с повторениями, но без повторяющихся строк

Question

Имеется массив из 1, 2, 3, 4. Необходимо составить все возможные комбинации из 3-х размерных рядов, элементы могут повторяться. Порядок элементов в строке не важен. Например: 114 = 411 = 141. Не могу найти подходящий алгоритм. Я нашел этот алгоритм, но не может быть повторений элементов типа 111 или 113, только 123,124 и т. Д. c.

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;
    }

Answer 1

Попробуйте это.

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);
}

и

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

вывод:

6 6 6 
6 6 7 
6 6 8 
6 6 9 
6 7 7 
6 7 8 
6 7 9 
6 8 8 
6 8 9 
6 9 9 
7 7 7 
7 7 8 
7 7 9 
7 8 8 
7 8 9 
7 9 9 
8 8 8 
8 8 9 
8 9 9 
9 9 9 

Answer 2

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);
                }
            }
        }
    }
}

Идея такова: мы берем тройку, вычисляем сумму квадратов и проверяем, была ли у нас уже тройка с этой суммой. одинаковые тройки будут иметь одинаковую сумму квадратов. сумма квадратов всегда будет в диапазоне 3-48. кроме того, сумма уникальна для каждой комбинации чисел, как вам и требуется.

Сложность равна O (N ^ 3), где N - размер массива. поскольку нам нужны комбинации из 3 элементов, я не думаю, что вы можете go ниже этого.

UPDATE: , чтобы сделать более общим, используйте HashSet для сумм вместо логический массив и выполнить 3 вложенных цикла по входному массиву. вычислите сумму квадратов и сравните с HashSet.

Оптимизация производительности: заранее вычислите квадраты каждого элемента в массиве, чтобы вам не приходилось вычислять их снова и снова.