Как распечатать X количество перестановок в Java? - PullRequest
Новая
       12

Как распечатать X количество перестановок в Java?

0 голосов
/ 05 ноября 2018

Код, который я написал, принимает элементы массива и проходит через массив, чтобы получить все перестановки. Но мне нужно, чтобы отображалось только определенное количество перестановок:

Окончательный код должен дать только 6 перестановок из 9 элементов (иными словами, выведите первые 60480 схем из общего количества 362880 выходов). Для простоты я работаю с 4-мя элементами в массиве, и я распечатываю все 24 аранжировки. Но мне нужен код для работы с любым количеством перестановок. Например, если мне нужно распечатать 1-перестановку, код должен распечатать первые 4 схемы - ABCD, ABDC, ACBD и ACDB. Я не уверен, как решить это. 

public static void main(String[] args) {
    // TODO Auto-generated method stub


    String[] myArray = {"A","B","C", "D"};
    int size = myArray.length; 
    permutation(myArray, 0, size-1);

    // Calculate Permutations
    int n=size;
    int r=6; // subject to change
    int p = n - r;
    int total=1;
    int total2=1;
    int total3=0;

    for (int top=n; top>0; top--)
    {
        total *= top;
    }

    if ((n-r<0))
    {
     System.out.println("r value cannot be greater than array size");
     total3=0;
    }
    else 
    {
        for (int bot=1; bot<=p; bot++)
        {
            if (p==0) // should be -- else if (p==0) -- after correction
            {
                total2=1;
            }
            else
            {
                total2 *= bot;
            }
        }
        total3 = total/total2;
    }

    System.out.printf("%d permutations of %d elements = %d\n",r,n,total3);
    // end calculation

}
// end main

// print array
public static void prtArray(String[] myArray, int size)
{
    for(int i=0; i<size; i++)
    {
        System.out.printf("%s", myArray[i]);
    }
    System.out.println();
}

// swap elements    
public static void swap(String[] myArray, int i, int j) {
    String temp;
    temp = myArray[i];
    myArray[i]=myArray[j];
    myArray[j]=temp;
}

// permutation 
private static void permutation(String[] myArray, int b, int e)
{
    if (b == e)
        prtArray(myArray, e+1); // accounts for array of size 1
    else
    {
        for(int i = b; i <= e; i++)
        {

            swap(myArray, i, b);
            permutation(myArray, b+1, e);
            swap(myArray, i, b);

        }
    }
}
}

1 Ответ

0 голосов
/ 05 ноября 2018

Я предполагаю, что вы не хотите, чтобы элемент повторялся при перестановке. например.

Если входной массив равен {1, 2, 3, 4}, то для длины 3: 123, 124 и т. Д. Являются допустимыми перестановками, но 122 или 111 - нет.

Чтобы избежать выбора элементов, которые уже выбраны, нам нужно передать массив visited в рекурсии. 

public class Main {
    // Maintain a global counter. After finding a permutation, increment this. 
    private static int count = 0;

    // pos is the current index, and K is the length of permutation you want to print, and N is the number of permutation you want to print.
    private static void printPermutations(int[] arr, int[] visited, int pos, int K, int N, String str) {

        // We have already found N number of permutations. We don't need anymore. So just return.
        if (count == N) {
            return;
        }

        if (pos == K) {
            System.out.println(str);
            count++; // we have found a valid permutation, increment counter.
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            // Only recur if the ith element is not visited.
            if (visited[i] == 0) {
                // mark ith element as visited.
                visited[i] = 1;
                printPermutations(arr, visited, pos + 1, K, N, str + arr[i]);
                // unmark ith element as visited.
                visited[i] = 0;
            }
        }

    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int[] visited = {0, 0, 0, 0}; // same as size of input array.
        count = 0; // make sure to reset this counter everytime you call printPermutations.
        // let's print first 4 permutations of length 3.
        printPermutations(arr, visited, 0, 3, 4, "");
    }
}

Выходы:

для N = 4 и K = 3 (т.е. первые 4 перестановки длины 3): 

printPermutations(arr, visited, 0, 3, 4, "");

123
124
132
134

для N = 4 и K = 4 (т.е. первые 4 перестановки длины 4): 

printPermutations(arr, visited, 0, 4, 4, "");

1234
1243
1324
1342
...