java - 查找所有有重复但没有重复行的组合

Question

有一个1、2、3、4的数组，需要将3个尺寸系列的所有可能的组合进行组合，元素可以重复。行中元素的顺序并不重要。例如: 114 = 411 = 141。 我找不到合适的算法。我找到了这个算法，但是不能有重复的元素，比如111或113，只有123,124等。

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