排列组合算法

组合算法

非递归算法

组合算法的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标代表的数被选中,为0则没选中。

初始化,将数组前n个元素置1,表示第一个组合为前n个数。

从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。

例如求5中选3的组合:

1   1   1   0   0   //1,2,3     
1   1   0   1   0   //1,2,4     
1   0   1   1   0   //1,3,4     
0   1   1   1   0   //2,3,4     
1   1   0   0   1   //1,2,5     
1   0   1   0   1   //1,3,5     
0   1   1   0   1   //2,3,5     
1   0   0   1   1   //1,4,5     
0   1   0   1   1   //2,4,5     
0   0   1   1   1   //3,4,5

c++代码如下:

class Combination {
public:
    void combination(int n, int m) {
        int *a = new int[n];
        for (int i = 0; i < m; i++)
            a[i] = 1;
        for (int i = m; i < n; i++)
            a[i] = 0;
        bool tag = true;
        while (tag) {
            displayArray(a, n);
            for (int i = 0; i < n - 1; i++)
                if (a[i] == 1 && a[i + 1] == 0) {
                    tag = true;
                    a[i] = 0;
                    a[i + 1] = 1;
                    moveZeros(a, i);
                    break; 
                }
                else
                    tag = false;
        }
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    // 0到n-1,把1移到最左边
    void moveZeros(int *a, int n) {
        int left = 0, right = 0;
        while (right < n) {
            if (a[left] == 1)
                left++;
            else if (a[left] == 0 && a[right] == 1) {
                int t = a[left];
                a[left] = a[right];
                a[right] = t;
                left++;
            }
            right++;
        }
    }
};

递归算法

从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止。

从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m。

c++代码如下:

class Combination {
public:
    void combination(int n, int m) {
        int *a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = 0;
        func(a, n, m, n);
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    void func(int *a, int n, int m, const int N) {
        if (m == 0) {
            displayArray(a, N);
            return;
        }
        for (int i = n - 1; i >= m - 1; i--) {
            a[i] = 1;
            func(a, i, m - 1, N);
            a[i] = 0;
        }
    }
};

排列算法

递归算法

如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)},显然,给定n个元素共有n!种不同的排列.

如果给定集合是{a,b,c,d},可以用下面给出的简单算法产生其所有排列,即集合(a,b,c,d)的所有排列有下面的排列组成:
(1)以a开头后面跟着(b,c,d)的排列
(2)以b开头后面跟着(a,c,d)的排列
(3)以c开头后面跟着(a,b,d)的排列
(4)以d开头后面跟着(a,b,c)的排列

这显然是一种递归的思路,于是我们得到了以下的c++代码实现:

class Permutation {
public:
    void permutation(int n) {
        int *a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = 0;
        func(a, 1, n);
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    void func(int *a, int m, const int n) {
        if (m == n + 1) {
            displayArray(a, n);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                a[i] = m;
                func(a, m + 1, n);
                a[i] = 0;
            }
        }
    }
};

非递归算法

<div class="div-border left-purple"> 全排列生成算法的一个重要思路,就是将集合A中的元素的排列,与某种顺序建立一一映射的关系,按照这种顺序,将集合的所有排列全部输出。这种顺序需要保证,既可以输出全部的排列,又不能重复输出某种排列,或者循环输出一部分排列。
字典序就是用此种思想输出全排列的一种方式。这里以A{1,2,3,4}来说明用字典序输出全排列的方法。
首先,对于集合A的某种排列所形成的序列,字典序是比较序列大小的一种方式。
以A{1,2,3,4}为例,其所形成的排列1234 < 1243,比较的方法是从前到后依次比较两个序列的对应元素,如果当前位置对应元素相同,则继续比较下一个位置,直到第一个元素不同的位置为止,元素值大的元素在字典序中就大于元素值小的元素。
上面的a1[1…4]=1234和a2[1…4]=1243,对于i=1,i=2,两序列的对应元素相等,但是当i=2时,有a1[2]=3 < a2[2]=4,所以1234 < 1243。
使用字典序输出全排列的思路是,首先输出字典序最小的排列,然后输出字典序次小的排列,……,最后输出字典序最大的排列。
这里就涉及到一个问题,对于一个已知排列,如何求出其字典序中的下一个排列。这里给出算法。
对于排列a[1…n],找到所有满足a[k] < a[k+1] (0 < k < n-1)的k的最大值,如果这样的k不存在,则说明当前排列已经是a的所有排列中字典序最大者,所有排列输出完毕。
在a[k+1…n]中,寻找满足这样条件的元素l,使得在所有a[l]>a[k]的元素中,a[l]取得最小值。也就是说a[l]>a[k],但是小于所有其他大于a[k]的元素。
交换a[l]与a[k].
对于a[k+1…n],反转该区间内元素的顺序。也就是说a[k+1]与a[n]交换,a[k+2]与a[n-1]交换,……,这样就得到了a[1…n]在字典序中的下一个排列。
这里我们以排列a[1…8]=13876542为例,来解释一下上述算法。首先我们发现,1(38)76542,括号位置是第一处满足a[k] < a[k+1]的位置,此时k=2。
所以我们在a[3…8]的区间内寻找比a[2]=3大的最小元素,找到a[7]=4满足条件,交换a[2]和a[7]得到新排列14876532,对于此排列的3~8区间,反转该区间的元素,将a[3]-a[8],a[4]-a[7],a[5]-a[6]分别交换,就得到了13876542字典序的下一个元素14235678。</div>

下面是该算法的实现代码:

class Permutation {
public:
    void permutation(int n) {
        int *a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i + 1;
        while (true) {
            displayArray(a, n);
            //找到k
            int k = n - 2;
            while (k != -1 && a[k] > a[k + 1])
                k--;
            if (k == -1)
                return;
            // 交换比k稍大的数
            int l = k + 1;
            for (int i = k + 1; i < n; i++)
                if (a[i] > a[k] && a[i] < a[l])
                    l = i;
            int t = a[k];
            a[k] = a[l];
            a[l] = t;
            //反转
            for (int i = 1; 2 * i < n - k; i++) {
                int t = a[k + i];
                a[k + i] = a[n - i];
                a[n - i] = t;
            }
        }
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,590评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 86,808评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,151评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,779评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,773评论 5 367
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,656评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,022评论 3 398
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,678评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 41,038评论 1 299
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,756评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,411评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,005评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,973评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,053评论 2 350
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,495评论 2 343

推荐阅读更多精彩内容