精华内容
下载资源
问答
  • Python实现排列组合从M个元素有序或者无序选取N个元素的集合。 import itertools '''无序排列''' c = list(itertools.combinations([1, 2, 3, 4], 2)) print(c) '''有序排列''' p = list(itertools....

    Python中实现排列组合,从M个元素中有序或者无序选取N个元素的集合。

    import itertools
    
    '''
    无序排列
    combinations(M个数的集合,选取N个数为一组)
    '''
    c = list(itertools.combinations([1, 2, 3, 4], 2))
    print(c)
    
    '''
    有序排列
    permutations(M个数的集合,选取N个数为一组)
    '''
    p = list(itertools.permutations([1, 2, 3, 4], 2))
    print(p)
    
    '''
    测试结果:
    [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
    [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
    '''
    
    展开全文
  • //////////////////////////////////////////////////////////////////...// 算法 : N 数字中选取 M , 打印所有可能组合 // ////////////////////////////////////////////////////////////////////////// ...
    //
    //
    // 算法 : 从 N 个数字中选取 M 个, 打印所有可能组合
    //
    //
    
    //
    // 使用一个辅助数组 aux[1..M] 用来记录 input[1..N] 中被选中元素的索引
    // 比如 input[i] 被选中, 那么中会有一项 aux[*] = i
    //
    
    //
    // 从后向前计算:
    // 基本思想是, 从 N 个元素中选取 M 个, 首先选取第 M 个, 然后在从剩下的选取 M - 1 个。
    //
    // 对于 aux[m] 有选择的数目: (从 input 的没被用到的最后一个) ~ input[m]。
    // 止于 input[m] 的原因是因为再向前的话, aux[0..m-1] 可以选择的 input 数目会不足。
    //
    // 这里 m 表示的是还剩几个元素没有选, 初始化的时候值为 M
    void combination1(char input[], const int N, int aux[], int m, const int M, int & counter)
    {
        for (int i = N; i >= m; i--)    // 从后向前
        {
            if (m >= 1)
            {
                aux[m - 1] = i - 1;     // 选取 input[i-1]
            }
    
            if (m > 1)                  // 还没选完, 从 input[0..i-1] 中选取剩下的 m-1 个元素
            {
                combination1(input, i - 1, aux, m - 1, M, counter);
            }
            else                        // 选择完毕
            {
                counter++;
    
                cout << "{ ";           // 根据 aux[j] 指定的下标, 输出 input[aux[j]]
                for (int j = 0; j <M; j++)
                {
                    cout << input[aux[j]] << " ";
                }
                cout << "}" << endl;
            }
        }
    }
    
    void combination1(char input[], const int N, const int M)
    {
        int * aux = new int[M];
        memset(aux, 0, sizeof(int) * M);
    
        int counter = 0;
    
        combination1(input, N, aux, M, M, counter);
    
        cout << "total : " << counter << endl;
    }
    
    //
    // 从前向后计算:
    // 基本思想是: 从 N 个元素选取 M个, 首先选取第 1 个, 其余 M - 1 个元素从剩下的元素中选取。
    //
    // [begin*************X******N-1]
    //              [0....m******M-1]
    // N - 1 - X = M - 1 - m
    // X = N - M + m
    // aux[m] 选择范围: [input[begin], input[X]]
    //
    // 这里的 m 表示选择了多少个元素, 初始值为 0
    void combination2(char input[], const int begin, const int N, int aux[], int m, const int M, int & counter)
    {
        for (int i = begin; i <= N - M + m; i++)    // 从前向后
        {
            if (m < M)
            {
                aux[m] = i;                         // 选择第 m 个元素
            }
    
            if (m < M - 1)                          // 没选择完, 从余下的 input[i+1..N] 中选择余下的元素
            {
                combination2(input, i + 1, N, aux, m + 1, M, counter);
            }
            else
            {
                counter++;
    
                cout << "[ ";
                for (int j = 0; j <M; j++)
                {
                    cout << input[aux[j]] << " ";
                }
                cout << "]" << endl;
            }
        }
    }
    
    void combination2(char input[], int N, int M)
    {
        int * aux = new int[M];
        memset(aux, 0, sizeof(int) * M);
    
        int counter = 0;
    
        combination2(input, 0, N, aux, 0, M, counter);
    
        cout << "total : " << counter << endl;
    }
    
    //
    // 回溯法
    // flag 大小和 input 相同
    // flag[i] 用来记录 input[i] 是否被选中
    // n 表示有多少个 input 元素参与了选择
    // m 表示选择了多少个元素
    void back_tracking(char input[], bool flag[], const int N, const int M, int n, int m, int & counter)
    {
        if (m == M)                 // 选满了 M 个
        {
            counter++;
    
            cout << "< ";
            for (int j = 0; j <N; j++)
            {
                if (flag[j])
                {
                    cout << input[j] << " ";
                }
            }
            cout << ">" << endl;
        }
        else if (m >= M || n >= N )     // n >= N 说明把 input 挑了个遍, 也没凑齐 M 个元素
        {
            return;
        }
        else
        {
            flag[n] = 1;                // 选取了 input[n]
            back_tracking(input, flag, N, M, n + 1, m + 1, counter);
    
            flag[n] = 0;                // 没有选择 input[n]
            back_tracking(input, flag, N, M, n + 1, m, counter);
        }
    }
    
    void back_tracking(char input[], int N, int M)
    {
        bool * flag = new bool[N];
        memset(flag, 0, sizeof(bool) * N);
    
        int counter = 0;
    
        back_tracking(input, flag, N, M, 0, 0, counter);
    
        cout << "total : " << counter << endl;
    }
    
    void select_M_from_N()
    {
        char input[] = "abcdef";
        //
        // 算法一
        combination1(input, strlen(input), 3);
    
        //
        // 算法二
        combination2(input, strlen(input), 3);
    
        //
        // 算法三
        back_tracking(input, strlen(input), 3);
    }

     

    转载于:https://www.cnblogs.com/happylong/p/4504341.html

    展开全文
  • NOI国家集训队论文集(1)全排列组合的递归规律:集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});...全排列组合,如果集合有4个元素,,...

    NOI国家集训队论文集

    (1)全排列组合的递归规律:

    集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合

    以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});其中n={1},s-n={2,3}

    通过以上例子,我们可以知道上述算法可以用递归来解决。

    我们取极端情况,如果集合s为空,那么说明不需要再进行递归。

    全排列组合,如果集合有4个元素,,则全排列组合的个数为 A(4,4)=4*3*2*1=24种,代码如下:

    package dataStructer;

    import java.util.Arrays;

    import java.util.LinkedList;

    import java.util.List;

    public class FullPermutation {//全排列组合

    private int n;

    public FullPermutation ()

    {

    this.n=0;

    }

    public void listAll(List candidate,String prefix)

    {

    if(candidate.isEmpty())

    {

    System.out.println(prefix);

    this.n++;

    }

    for(int i=0;i

    {

    List temp=new LinkedList(candidate);//转换成linkList,移除一个对象是在不影响原来队列的基础上的

    String s1=prefix+temp.remove(i);//用于保存排列组合生成的结果

    listAll(temp,s1);//注意,这里temp和s1都是全新的集合和字符串,并不是一直对一个集合来进行操作

    }

    }

    public int getN() {

    return n;

    }

    public void setN(int n) {

    this.n = n;

    }

    public static void main(String[] args) {

    String []arr={"1","2","3","4"};

    FullPermutation f=new FullPermutation();

    f.listAll(Arrays.asList(arr),"");

    System.out.println("所有的排列个数:"+f.getN());

    }

    }

    (2)m个数据集合中选出n个数据(有序)

    m个数据集合中选出n个数据规律为:get({m},n)=t+get(集合{m-t},m-t的大小)

    考虑极端的情况,如果集合m里只取一个元素,那么直接把这个元素取出来即可。

    如何集合有4个元素,取出其中的两个有序元素个数为A(4,2)=4*3=12

    package dataStructer;

    import java.util.ArrayList;

    import java.util.Arrays;

    import java.util.LinkedList;

    import java.util.List;

    public class mAn {

    private int all;

    public mAn()

    {

    this.all=0;

    }

    public int getAll() {

    return all;

    }

    public void setAll(int all) {

    this.all = all;

    }

    public static void main(String[] args) {

    String[] n ={"1","2","3","4"};

    mAn m=new mAn();

    List lst = Arrays.asList(n);

    m.take("",2,lst);

    System.out.println(m.getAll());

    }

    public void take(String s, int total, List lst) {

    for (int i = 0; i < lst.size(); i++) {

    //System.out.println("i="+i);

    List templst=new LinkedList(lst);

    String n = (String) templst.remove(i);// 取出来的数字

    String str = s + n;

    if (total == 1) {

    System.out.println(str);//以最极端 n个里面只取一个,直接把取出来的结果输出即可

    //total=all;

    all++;

    } else {

    int temp=total-1;//在同一层中total总量不能减,不能再原有变量的基础上

    take(str, temp, templst);// 这里的temp以及templst都是全新的变量和集合

    }

    }

    }

    }

    版权声明:本文为博主原创文章,未经博主允许不得转载。

    展开全文
  • (1)全排列组合的递归规律:集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});...全排列组合,如果集合有4个元素,则全排列组合的个数为 A...

    (1)全排列组合的递归规律:

    集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合

    以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});其中n={1},s-n={2,3}

    通过以上例子,我们可以知道上述算法可以用递归来解决。

    我们取极端情况,如果集合s为空,那么说明不需要再进行递归。

    全排列组合,如果集合有4个元素,则全排列组合的个数为 A(4,4)=4*3*2*1=24种,代码如下:

    package dataStructer;

    import java.util.Arrays;

    import java.util.LinkedList;

    import java.util.List;

    public class FullPermutation {//全排列组合

    private int n;

    public FullPermutation ()

    {

    this.n=0;

    }

    public void listAll(List candidate,String prefix)

    {

    if(candidate.isEmpty())

    {

    System.out.println(prefix);

    this.n++;

    }

    for(int i=0;i

    {

    List temp=new LinkedList(candidate);//转换成linkList,移除一个对象是在不影响原来队列的基础上的

    String s1=prefix+temp.remove(i);//用于保存排列组合生成的结果

    listAll(temp,s1);//注意,这里temp和s1都是全新的集合和字符串,并不是一直对一个集合来进行操作

    }

    }

    public int getN() {

    return n;

    }

    public void setN(int n) {

    this.n = n;

    }

    public static void main(String[] args) {

    String []arr={"1","2","3","4"};

    FullPermutation f=new FullPermutation();

    f.listAll(Arrays.asList(arr),"");

    System.out.println("所有的排列个数:"+f.getN());

    }

    }

    (2)m个数据集合中选出n个数据(有序)

    m个数据集合中选出n个数据规律为:get({m},n)=t+get(集合{m-t},m-t的大小)

    考虑极端的情况,如果集合m里只取一个元素,那么直接把这个元素取出来即可。

    如何集合有4个元素,取出其中的两个有序元素个数为A(4,2)=4*3=12

    package dataStructer;

    import java.util.ArrayList;

    import java.util.Arrays;

    import java.util.LinkedList;

    import java.util.List;

    public class mAn {

    private int all;

    public mAn()

    {

    this.all=0;

    }

    public int getAll() {

    return all;

    }

    public void setAll(int all) {

    this.all = all;

    }

    public static void main(String[] args) {

    String[] n ={"1","2","3","4"};

    mAn m=new mAn();

    List lst = Arrays.asList(n);

    m.take("",2,lst);

    System.out.println(m.getAll());

    }

    public void take(String s, int total, List lst) {

    for (int i = 0; i < lst.size(); i++) {

    //System.out.println("i="+i);

    List templst=new LinkedList(lst);

    String n = (String) templst.remove(i);// 取出来的数字

    String str = s + n;

    if (total == 1) {

    System.out.println(str);//以最极端 n个里面只取一个,直接把取出来的结果输出即可

    //total=all;

    all++;

    } else {

    int temp=total-1;//在同一层中total总量不能减,不能再原有变量的基础上

    take(str, temp, templst);// 这里的temp以及templst都是全新的变量和集合

    }

    }

    }

    }

    展开全文
  • (1)全排列组合的递归规律: 集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合 以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});...全排列组合,如果集合有4个元素,则全
  • 从n个中选取m个数的所有组合

    千次阅读 2020-06-04 21:27:04
    n个数1,2,...,n,n个任意选m个数,输出所有不同组合,共有C(n,m)种不同组合。 如n=4,m=2,会产生如下输出: 1 2 1 3 2 3 1 4 2 4 3 4 如n=5,m=3,会产生如下输出: 1 2 3 1 2 4 1 3 4 2 3 4 1...
  • nn>0)nn>0)个数,从中选取mn>m>0)mn>m>0)个数,找出所有的组合情况(不分顺序)。这样的组合共有 Cmn=n×(n−1)×... 一个数组 data 有 n 个元素,从中选取 m 个数的组合 arr,使用递归算法实现是这样一
  • 假如现在有n个数,分别里面选择m个出来,那么一共有多少种不同的组合呢,分别是哪些呢?利用计算机的计算力,采用回溯算法很容易求解程序源代码如下:#include<iostream>#include<algorithm>using ...
  • 这道题比较简单,是常见的排列组合问题,由于之前的博客文章已经讨论的排列问题(集合的全排列),在此我们仅仅讨论一下组合的问题,n个元素集合m个元素的子集合: 我们在这里介绍的是递归的方法,思路如下: ...
  • 从n个数组任意选取个元素的所有组合,对于这个问题,我们在直观上感觉很容易,但是用程序实现时则发现用for循环解决不了问题,因为n是随意的。 在这里,我们用递归的思想,对于数据[1, 3, 4]; [2, 5]; [6, 7];...
  • Python程序员面试算法宝典---解题总结: 第7章 排列组合与概率 7.5 如何以等概率地大小为n的数组中选取m个整数 题目: 分析: 蓄水池抽样问题。 假设已经选取了k个元素,剩余待选元素有m-k个,剩余元素有n-k个。 ...
  • 一个数组 data 有 N 个元素,从中选取 M 个数的组合 array(不分顺序),可使用递归算法实现,过程如下: 选择 data 的第 1 个元素为 array 的第一个元素,即:array[0] = data[0]; 在 data 第一个元素之后的其它...
  • n个数中选m个数的全组合...

    千次阅读 2013-11-21 21:13:41
    首先从n个中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到n-(m-1)个数中选取1个数为止。 b. 从n个中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m。 下面是递归方法的实现...
  • n的数目较少的时候,可将元素的所有组合都列举出来,每个元素都有 “选” 和 “不选” 两种情况,总共就有2^n种 思路: 假设输入的M值为8,可供选择的数为 【1、5、7】 调用①solve(0,8)...
  • 特此说明,本文算法改自于《一个数组中找出 N 个数,其和为 M 的所有可能--最 ...举个例子,数组 [1, 2, 3, 4] 中选取 2 个元素,求和为 5 的所有可能。答案是两组组合: 1,4 和 2,3。 假设封装函数为 search: ...
  • 本题的关键在随意取几个数, 因此和以前解过的true or false问题思路一样....这n个, 每一个数都有选取和不选取两种情况, 比如第一个数如果选取, 那么剩余的9 个元素其和应该为m -1, 如果第一个数不选取,
  • 摘要 将n个数字放到一个长度为n的数组。...令0-1数组前m个元素都为1(此时就已经代表了一种组合) 循环切换: 利用for找到该0-1数组第一个存在“1 0”的位置(即前一位置为1,后一位置为0),对调两者位置(...
  • n个不同元素每次取出m个不同元素(0≤m≤n),不管其顺序合成一组,称为从n个元素中不重复地选取m个元素的一个组合。所有这样的组合的总数称为组合数,这个组合数的计算公式为: or 那么我们应该怎么用程序的...
  • java排列组合算法(MN

    千次阅读 2017-05-18 18:04:36
    从M长度的容器每次选取N个元素 举例,从(a,b,c,d,e)取两个元素,则为(ab) (ac) (ad)(ae)(bc)(bd)(be)(cd)(ce)(de)import java.util.ArrayList; import java.util.Collections; import ...
  • 从n个元素中挑选m个元素,有多少组组合,可以重复选择。 输入:3 3 输出:10 解析:三个元素中选取三个元素,可以重复选,共有多少组组合。111 112 113 122 123 133 222 223 233 333 一共十组组合,注:121 112...
  • 信息学组合数学

    2019-10-06 04:45:04
    组合数:\(N\)个元素中选取\(M\)个元素,选取顺序无关,记做\(C(N, M)\)。 \(C(N, M)=\frac{N!}{M!(N-M)!}=C(N-1, M-1)+C(N-1, M)\) 排列数:\(N\)个元素中选取\(M\)个元素,选取顺序有关,记做\(P(N, M)\)。...
  • 组合

    2014-05-09 21:41:57
    算法说明:从n个数中选m个数,可以分解为以下两步(1)首先从n个中选取编号最大的数,然后在剩下的n-1个数中选取m-1个数,直到n-(m-1)个数中选取1个数为止。 /*求a[n]中选取m个数的可能组合。数组a[n]表示...
  • 组合的定义

    2019-10-01 19:37:44
    n个不同元素每次取出m个不同元素(0≤m≤n),不管其顺序合成一组,称为从n个元素中不重复地选取m个元素的一个组合。所有这样的组合的总数称为组合数,这个组合数的计算公式为 重复组合(combination ...
  • 排列组合的基本公式

    万次阅读 2018-08-12 17:16:12
    排列和排列数 从n个不同元素,任取mm≤n)个元素(被取出的元素各不相同),按照一定的顺序排成一列,叫做从n个...=n),不管其顺序合成一组,称为 n 个元素中不重复地选取 m 个元素的一个组合。所有这样的组...
  • 从n个不同元素中选取m个元素进行排列,其中的每种组合都重复了,重复的次数就是m的全排列数。比如,1,2,3三个元素中选取2个元素进行排列,排列的结果是[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]。1和...
  • Java 全排列与组合

    2021-05-19 09:50:03
    Permutation全排列概念分析代码展示组合概念枚举1-n所有...一般地说,n个不同元素,任取m(m≤n)个元素,按照一定的顺序排成一列,这就叫做从n个元素中取出m个元素的一个排列。 公式: 当 m=n 时,便称为全排列 此

空空如也

空空如也

1 2 3 4 5
收藏数 94
精华内容 37
关键字:

从m中选取n个元素组合