文档章节

C#求数组中元素的全排列

北风其凉
 北风其凉
发布于 2014/05/02 14:09
字数 681
阅读 1825
收藏 4

1.算法描述

全排列的第一项是该数组的升序排列,最后一项是该数组的降序排列。本文中用到的了一个函数FindNextArray:从升序排列开始,不断使用函数FindNextArray,可以遍历全部排列,最终到达数组中元素的降序排列。

FindNextArray函数的实现思路:

设有数组array为原数组的一个排列

1)找出数组的最大值

2)从后向前找:找到第一组array[i]>array[i-1]的数,以i位置为signer

3)从signer向后找:找到大于且最接近于array[signer-1]的数array[t]

4)将找到的array[t]和array[signer-1]互换

5)为位置signer之后的元素升序排序

所得的新数组即为原数组的一个新排列

2.相关函数

/// <summary>
/// 输出一个数组的全排列
/// </summary>
/// <param name="array"></param>
private static void PrintFullPermutation(int[] array)
{
    //0.合法性校验
    if (array == null || array.Length == 0)
    {
        return;
    }

    //1.复制一个新数组:修改时在临时数组中修改
    int[] temp = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
    {
        temp[i] = array[i];
    }

    //2.将新数组升序排列
    int itemp;
    for (int i = 0; i < temp.Length; i++)
    {
        for (int j = i; j < temp.Length; j++)
        {
            itemp = array[i];
            array[i] = array[j];
            array[j] = itemp;
        }
    }

    //3.依次寻找并打印全排序
    PrintArray(temp);
    while (!isDesc(temp))
    {
        FindNextArray(temp);
        PrintArray(temp);
    }
}

/// <summary>
/// 打印数组
/// </summary>
/// <param name="array">数组</param>
private static void PrintArray(int[] array)
{
    for (int i = 0; i < array.Length; i++)
    {
        Console.Write(array[i].ToString() + '\t');
    }
    Console.WriteLine();
}

/// <summary>
/// 判断一个数组内元素是否降序排列
/// </summary>
/// <param name="array">数组</param>
/// <returns></returns>
private static bool isDesc(int[] array)
{
    int temp=array[0];
    for (int i = 1; i < array.Length; i++)
    {
        if (array[i] > array[i - 1])
        {
            return false;
        }
    }
    return true;
}

/// <summary>
/// 找到下一组排列
/// </summary>
/// <param name="array"></param>
private static void FindNextArray(int[] array)
{
    //1.找出数组的最大值
    int max = array[0];
    for (int i = 1; i < array.Length; i++)
    {
        if (max < array[i])
        {
            max = array[i];
        }
    }

    //2.从后向前找:找到第一组后数大于前数,以后数位置为signer
    int signer = array.Length - 1;
    for (int i = array.Length - 1; i > 0; i--)
    {
        if (array[i] > array[i - 1])
        {
            signer = i;
            break;
        }
    }

    //3.从signer向后找:找到大于且最接近于array[signer-1]的数array[t]
    int t = signer;
    for (int i = signer; i < array.Length; i++)
    {
        if (array[i] > array[signer - 1] && array[i] < max)
        {
            t = i;
            max = array[t];
        }
    }

    //4.将找到的array[t]和array[signer-1]互换
    int temp = array[t];
    array[t] = array[signer - 1];
    array[signer - 1] = temp;

    //5.为signer之后的元素升序排序
    for (int i = signer; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[i] > array[j])
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

3.Main函数调用

static void Main(string[] args)
{
    //求1234四个数字的全排列
    int[] array = new int[] { 1, 2, 3, 4 };
    PrintFullPermutation(array);

    Console.ReadLine();
}

4.程序运行示例

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 120
博文 498
码字总数 463522
作品 4
朝阳
程序员
私信 提问
全排列 Permutations

问题: Given a collection of distinct numbers, return all possible permutations. For example, have the following permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ......

叶枫啦啦
2017/09/04
7
0
求一个集合S中m个元素的所有排列以及一个数组A的全排列—递归实现版完整代码

  说明,本文全文代码均用dart语言实现。   求一个集合S中m个元素的所有排列情况,并打印,非常适合用递归的思路实现。本文给出了两种实现方法,一种是给定的填充排列数组长度是固定的,...

Burkut
05/13
0
0
47. Permutations II

使用递归算法特性:必须的终止条件子问题比原来的问题小子问题可以再递归求解子问题的解能够组成大问题的解 a bc b ac c ba

datacube
2016/07/05
5
0
next_permutation(全排列算法)

STL提供了两个用来计算排列组合关系的算法,分别是nextpermutation和prevpermutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列{a,...

angel_kitty
2017/02/12
0
0
Leetcode46——Permutations

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given a collection of distinct numbers, return all possible permutations. For example, have the following permutatio......

Quincuntial
2017/04/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS3

一.复杂选择器 1.兄弟选择器 具备相同父级元素的平级元素之间称为兄弟元素 注意:兄弟选择器,只能往后,不能往前找 (1).相邻兄弟选择器,获取紧紧挨着某元素后面的兄弟元素 选择器1+选择器2...

wytao1995
19分钟前
3
0
Jmeter录制

1. 加HTTP(s) Test Script Recorder 2. 在 recorder下面加reocrding controller 3. 在HTTP(s) Test Script Recorder中设置下面几项 4. browser设置proxy, 注意端口要和step3中jmeter中的一致......

Rebecca_Hu
24分钟前
3
0
DIV+CSS忽悠前端小白

在大约两年前,DIV+CSS是一对很诱人的组合,会用DIV+CSS制作网页的人,常常会被人赞以大拇指的,记得06年初的时候,我用 div+css布局的一个纯静态网站还拿了学校网页设计比赛的一个奖。 今天...

前端老手
27分钟前
3
0
Win10子系统 linux(Ubuntu18.04) 安装Docker

1)原文件备份 sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak 2)编辑源列表文件 sudo vim /etc/apt/sources.list 3)将原来的列表删除,添加如下内容(中科大镜像源) deb http...

jxldjsn
29分钟前
3
0
Ubuntu16.04安装Qt5.12.2

Ubuntu16.04安装Qt5.12.2 第一步:下载文件 https://download.qt.io/official_releases/qt/5.12/5.12.2/ 第二步:安装依赖库 sudo apt-get install build-essential sudo apt-get install li......

shzwork
35分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部