Печать всех возможных комбинаций nCr в Java

Question

Печать всех возможных комбинаций nCr в Java

Я пытаюсь распечатать все возможности nCr, которые являются комбинациями, когда порядок не имеет значения. Таким образом, 5C1 есть 5 возможностей: 1, 2, 3, 4, 5. 5C2 есть 10 возможностей: 1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5.

Я сделал функции, которые печатают то, что я хочу для r = 2, r = 3 и r = 4, и я вроде как вижу шаблон, но я не могу создать рабочий метод для переменной r:

public void printCombinationsChoose2(int n, int k) //for when k = 2
{
    for (int a = 1; a < n; a++)
    {
        for (int b = a + 1; b <= n; b++)
        {
            System.out.println("" + a + " " + b);
        }
    }
}

public void printCombinationsChoose3(int n, int k) //for when k = 3
{
    for (int a = 1; a < n - 1; a++)
    {
        for (int b = a + 1; b < n; b++)
        {
            for (int c = b + 1; c <= n; c++)
            {
                System.out.println("" + a + " " + b + " " + c);
            }
        }
    }
}

public void printCombinationsChoose4(int n, int k) //for when k = 4
{
    for (int a = 1; a < n - 2; a++)
    {
        for (int b = a + 1; b < n - 1; b++)
        {
            for (int c = b + 1; c < n; c++)
            {
                for (int d = c + 1; d <= n; d++)
                {
                    System.out.println("" + a + " " + b + " " + c + " " + d);
                }
            }
        }
    }
}

public void printCombinations(int n, int k) //Doesn't work
{
    int[] nums = new int[k];
    for (int i = 1; i <= nums.length; i++)
        nums[i - 1] = i;

    int count = 1;

    while (count <= k)
    {
        for (int a = nums[k - count]; a <= n; a++)
        {
            nums[k - count] = a;

            for (int i = 0; i < nums.length; i++)
                System.out.print("" + nums[i] + " ");
            System.out.println();
        }
        count++;
    }
}

Так что я думаю, что расположение моего последнего метода правильное, но я просто не делаю правильные вещи, потому что когда я вызываю printCominbations(5, 2)печатает

когда это должно быть то, что я сказал ранее для 5C2.

Редактировать Последний пример был плохим. Это лучше, чтобы проиллюстрировать, что он делает неправильно: printCombinations(5, 3) дает это:

Как мне это сделать:

5

java statistics ncr

Источник

user772985 02 окт '11 в 13:36

5 ответов

Решение

Первая точка, где ваш код отклоняется от ожидаемого, находится здесь:

...
1 2 5 
1 2 5    <-- first bad output
1 3 5
...

Итак, задайте себе три вещи:

Что должно было произойти в этой строке кода с заданным состоянием переменных?
Почему мой код не делает именно это?
Что нужно изменить, чтобы добиться этого?

Ответ для первой части таков:

Это должно было увеличить 2 в 3 и он должен был установить следующие цифры 4, 5... похоже на инициализацию nums,

Вторая и третья часть снова ваша.

КСТАТИ: Когда вы вернетесь, потому что вам нужна дополнительная помощь, пожалуйста, подробно объясните, что вы уже сделали, очистите и немного укоротите вопрос.

4

Источник

user947357 02 окт '11 в 18:09

Хорошо... Каково решение, когда мы знаем, что нам нужны петли, а не их число? RECURSION... Вам нужно использовать рекурсивную реализацию. Имейте это в виду: В ЛЮБОЕ время вам нужны циклы, но количество вложенных циклов может быть известно только во время выполнения, исходя из конкретных параметров проблемы, вы должны использовать рекурсивные методы... Я дам вам некоторое время, чтобы попробовать сам, я вернусь, чтобы дать вам окончательную реализацию...

1

Источник

user959156 02 окт '11 в 15:06

Я сделал это в C++

#include <iostream>

using namespace std;
#define ARR_LIMIT 100
int arr[ARR_LIMIT];

void _ncr(int N,int R, int n,int r , int start )
{
    if(r>0)
    {
        for(int i = start ; i <= start + (n-r); i++)
        {
            arr[R-r] = i;
            _ncr(N,R,N-i, r-1, i+1 );
        }
    }
    else
    {
        for(int i=0;i<R;i++)
        {
            cout << arr[i] << " ";
            if(i==R-1)
                cout<<"\n";
        }
    }

}

void ncr(int n,int r)
{
    //Error checking of parameters
    bool error = false;
    if( n < 1)
    {
        error = true;
        cout<< "ERROR : n should be greater 0 \n";
    }
    if( r < 1)
    {
        error = true;
        cout<< "ERROR : r should be greater 0 \n";
    }
    if(r > n)
    {
        error = true;
        cout<< "ERROR : n should be greater than or equal to r \n";
    }
    // end of Error checking of parameters
    if(error)
        return;
    else
        _ncr(n,r,n,r,1);
}

int main()
{
    int n,r;
    cout << "Enter n : ";
    cin >> n;
    cout << "Enter r : ";
    cin >> r;
    ncr(n,r);
    return 0;
}

1

Источник

user2114956 27 фев '13 в 11:01

Расположение функции printCombination() кажется неправильно. Цикл while будет повторяться два раза, для count = 1 а также count = 2,

когда count = 1только значения в nums[0][here] изменится, так как в этом случае k - count = 1, Следовательно,
1,2
1,3
1,4 и
1,5.

И когда count = 2только значения в nums[here][1] будет меняться, так как здесь k - count = 0, следовательно
1,5
2,5
3,5
4,5 и
5,5

0

Источник

user773465 02 окт '11 в 14:26

Другие вопросы по тегам java statistics ncr

user959156 03 окт '11 в 06:56 2011-10-03 06:56 · Accepted Answer · 2011-10-03 06:56

Как насчет этого:

public class Test {

    public static void main(final String[] args) {
        print_nCr(7, 4);
    }

    public static final void print_nCr(final int n, final int r) {
        int[] res = new int[r];
        for (int i = 0; i < res.length; i++) {
            res[i] = i + 1;
        }
        boolean done = false;
        while (!done) {
            System.out.println(Arrays.toString(res));
            done = getNext(res, n, r);
        }
    }

    /////////

    public static final boolean getNext(final int[] num, final int n, final int r) {
        int target = r - 1;
        num[target]++;
        if (num[target] > ((n - (r - target)) + 1)) {
            // Carry the One
            while (num[target] > ((n - (r - target)))) {
                target--;
                if (target < 0) {
                    break;
                }
            }
            if (target < 0) {
                return true;
            }
            num[target]++;
            for (int i = target + 1; i < num.length; i++) {
                num[i] = num[i - 1] + 1;
            }
        }
        return false;
    }
}

Ключом к этому решению для меня было посмотреть на проблему как на систему нумерации, и вы хотите увеличивать число на единицу, и каждый раз, когда вы достигаете верхней границы, вы просто переносите излишки на левую и... Вы просто нужно правильно реализовать алгоритм увеличения...