數(shù)組的排列

生成數(shù)組的排列是一項(xiàng)常見的計(jì)算任務(wù)。給定一組不同元素，我們?nèi)绾斡?jì)算這些元素的所有可能排列？

遞歸算法

排列生成的一種經(jīng)典算法采用遞歸。核心思想是將數(shù)組中的每個(gè)元素視為潛在的第一個(gè)元素，然后遞歸地排列剩余元素以找到從第一個(gè)元素開始的所有可能組合：

// Recursive method for permutation generation
public static void permute(int[] arr, int k) {
    for (int i = k; i < arr.length; i++) {
        // Swap elements at positions k and i
        Collections.swap(arr, k, i);
        // Recursively permute the remaining elements
        permute(arr, k + 1);
        // Restore original order of elements
        Collections.swap(arr, k, i);
    }
    if (k == arr.length - 1) {
        // Once all elements are permuted, print the current permutation
        System.out.println(Arrays.toString(arr));
    }
}

在此算法中，參數(shù) k跟蹤數(shù)組中的當(dāng)前位置。最初，k 設(shè)置為 0，表示第一個(gè)元素。對(duì)于每個(gè)位置 k，它迭代剩余的元素，將它們與位置 k 處的元素交換，并從位置 k 1 開始遞歸排列數(shù)組的其余部分。這有效地考慮了從每個(gè)元素開始的所有可能的排列。

不同元素的非遞歸算法

另一種非遞歸算法該算法適用于數(shù)組中所有元素都不同的情況。它通過迭代交換元素來構(gòu)建排列以實(shí)現(xiàn)特定模式：

for (int tail = arr.length - 1; tail > 0; tail--) {
    // Find the first decreasing element from the end
    if (arr[tail - 1] < arr[tail]) {
        // Find the last element greater than the decreasing element
        int s = arr.length - 1;
        while (arr[tail - 1] >= arr[s]) {
            s--;
        }
        // Swap the decreasing element with the greater element
        swap(arr, tail - 1, s);
        // Reverse the order of elements after the swap
        reverse(arr, tail);
        break;
    }
}

該算法從數(shù)組中元素的升序序列開始。它從右向左掃描數(shù)組，尋找第一個(gè)遞減的元素。一旦找到遞減的元素，它就會(huì)將其與數(shù)組尾部大于它的最小元素交換。最后，它反轉(zhuǎn)尾部元素的順序以獲得下一個(gè)排列。

相同元素的非遞歸算法

如果數(shù)組中的元素并不不同，使用 HashMap 將元素映射到其索引可以處理潛在的重復(fù)：

// Create a HashMap to map elements to their indices
Map<E, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    map.put(arr[i], i);
}
// Sort the array in ascending order
Arrays.sort(arr);
// Initialize the index array
int[] ind = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    ind[i] = map.get(arr[i]);
}

與正確的映射和索引，相同的非遞歸算法可以生成所有排列，適當(dāng)?shù)靥幚碇貜?fù)元素。

以上是我們?nèi)绾紊蓴?shù)組的所有可能排列，同時(shí)處理不同元素和非不同元素？的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！