开源中文网

您的位置: 首页 > 编程开发 > Java语言设计 > 正文

N个数选M(M<=N)个数,打印出所有可能组合,Java(递归)/C

来源:  作者:

import java.util.Set;
import java.util.HashSet;

public class Zuhe {
    static void lottery(int a[], int start_index, int end_index,
            int needed_balls, Set<Integer> already_chosen) {
        if (needed_balls == 0) {
            System.out.println(already_chosen);
            return;
        }
        for (int i = start_index; i <= end_index - needed_balls + 1; i++) {
            already_chosen.add(a[i]);
            lottery(a, i + 1, end_index, needed_balls - 1, already_chosen);
            already_chosen.remove(a[i]);
        }
    }

    public static void main(String[] args) {
        lottery(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 0, 9, 4,
                new HashSet<Integer>());
    }
}


#include <stdio.h>

const int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
const int n = 10;
int c[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };    
// 0 means not covered; 1 means chosen; 2 means not chosen.

const int limit = 2; 
// every element in c, its value shoudn't exceed this number.

const int needed_balls = 10;

int debug = 0;     
// 1 means prints the detailed process.


// check it's in the legal range.

// and check its dependency with others.

int legal (int c[], int k)
{
    if (c[k] == 1 || c[k] == 2)
    {
        return 1;
    }
    return 0;
}


// return : 1 means a solution is reached

int solution (int c[])
{
    int i = 0, sum = 0;
    for (= 0; i < n; i++)
    {
        if (c[i] == 1)
            sum++;
    }
    if (sum == needed_balls)
    {
        return 1;
    }
    return 0;
}

void print (int c[])
{
    int i = 0;
    for (= 0; i < n; i++)
    {
        if (c[i] == 1)
            printf ("%d ", a[i]);
    }
    printf ("\n");
}

void _debug_print (int c[])
{
    int i = 0;
    for (= 0; i < n; i++)
    {
        printf ("%d ", c[i]);
    }
    printf ("\n");
}

void lottery ()
{
    int k = 0, r;

    while (>= 0)
    {
        if (>= n)
        {
            if (debug)
                printf ("%d exceeds the array's valid index, go back to the above level\n", k);
            k--;
            continue;
        }
        c[k]++;
        if (debug)
            _debug_print (c);

        if (c[k] > limit)
        {
            if (debug)
                printf ("%d exceeds the value range, go back to the above level\n", c[k]);
            c[k] = 0;
            k--;
            continue;
        }
        r = legal (c, k);
        if (r)
        {
            if (solution (c))
            {
                if (debug)
                    printf ("found a solution\n");
                print (c);
            }
            else
            {
                if (debug)
                    printf ("%d seems to be a valid choice, go to the next level\n", c[k]);
                k++;
            }

        }
        else
        {
            if (debug)
                printf ("%d is not a valid choice, stay on the same level\n", c[k]);
        }

    }
}

int main ()
{
    
// debug = 1;

    lottery ();
    return 1;
}


Tags:个数
关于开源中文网 - 联系我们 - 广告服务 - 网站地图 - 版权声明