1 和 0 数组的所有唯一排列

问题描述 投票:0回答:1

我想要数组的所有唯一排列,例如:

int[] arr = { 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

我有一个可以工作的代码,我将在下面粘贴它,问题是它在彼此之间交换 0,在彼此之间交换 1,我想跳过这些排列,因为它们不相关。我以为我只需要组合,但同样,只有 {1,0} 的数组会返回自身,但 [0,1] 也与我相关。

编辑:通过跳过,我的意思是最好在生成之前尽快执行此操作,以节省一些时间,因为数组很大并且已经需要一段时间了。

代码:

static IEnumerable<int[]> GeneratePermutations(int[] arr)
    {
        int n = arr.Length;
        int[] indexes = new int[n];
        int[] currentPermutation = new int[n];

        for (int i = 0; i < n; i++)
        {
            indexes[i] = i;
            currentPermutation[i] = arr[i];
        }

        yield return currentPermutation;

        while (NextPermutation(indexes))
        {
            for (int i = 0; i < n; i++)
            {
                currentPermutation[i] = arr[indexes[i]];
            }
            yield return currentPermutation;
        }
    }

    static bool NextPermutation(int[] indexes)
    {
        int n = indexes.Length;
        int i = n - 2;

        while (i >= 0 && indexes[i] >= indexes[i + 1])
        {
            i--;
        }

        if (i == -1)
        {
            return false; // All permutations generated.
        }

        int j = n - 1;
        while (indexes[i] >= indexes[j])
        {
            j--;
        }

        Swap(ref indexes[i], ref indexes[j]);

        int left = i + 1;
        int right = n - 1;
        while (left < right)
        {
            Swap(ref indexes[left], ref indexes[right]);
            left++;
            right--;
        }

        return true;
    }

    static void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

没有必要调整当前的代码,我愿意接受新的解决方案或阅读的内容,这将为我指明正确的方向,谢谢!

c# arrays permutation
1个回答
0
投票

由于我得到的只是愤怒的评论,我确实找到了一个有效的解决方案,并且只生成独特的排列:

    static IEnumerable<int[]> GenerateUniquePermutations(int[] array)
    {
        // Sort the array to group identical permutations together
        Array.Sort(array);

        while (true)
        {
            int[] uniquePermutation = (int[])array.Clone();
            yield return uniquePermutation;

            // Find the next lexicographically greater permutation
            int i = array.Length - 2;
            while (i >= 0 && array[i] >= array[i + 1])
            {
                i--;
            }

            if (i < 0)
            {
                // All permutations generated
                break;
            }

            int j = array.Length - 1;
            while (array[j] <= array[i])
            {
                j--;
            }

            // Swap elements at i and j
            Swap(array, i, j);

            // Reverse the elements after i
            Reverse(array, i + 1, array.Length - 1);
        }
    }

    static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    static void Reverse(int[] array, int start, int end)
    {
        while (start < end)
        {
            Swap(array, start, end);
            start++;
            end--;
        }
    }

感谢您的反对票,希望它对搜索它的人有所帮助。

© www.soinside.com 2019 - 2024. All rights reserved.