Question

Перебор сочетаний из n-элементного множества по k. С++, паскаль абс или питон

Answer 1

int X[100];

int N;

void Swap(int a,int b)

{

int t=X[a];

X[a]=X[b];

X[b]=t;

}

void Generate(int k)

{

if (k==N)

{

for(int i=0;i<N;i++)

std::cout<<X[i]<<" ";

std::cout<<"\n";

}

else

{

for(int j=k;j<N;j++)

{

Swap(k,j);

Generate(k+1);

Swap(k,j);

}

}

}

int main()

{

std::cout<<"N=";

std::cin>>N;

for(int i=0;i<N;i++)

X[i]=i+1;

Generate(0);

}

Answer 2

Для перебора сочетаний из n-элементного множества по k можно использовать рекурсивный алгоритм или итеративный подход. Вот примеры реализации на C++, Pascal (Pascal ABC), и Python:

C++

cppCopy code
#include <iostream>
#include <vector>

void combinationsUtil(std::vector<int>& combination, int n, int k, int start) {
    if (k == 0) {
        // Выводим текущую комбинацию
        for (int num : combination) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
        return;
    }

    // Генерируем сочетания рекурсивно
    for (int i = start; i <= n - k + 1; ++i) {
        combination.push_back(i);
        combinationsUtil(combination, n, k - 1, i + 1);
        combination.pop_back();
    }
}

void combinations(int n, int k) {
    std::vector<int> combination;
    combinationsUtil(combination, n, k, 1);
}

int main() {
    int n = 5;
    int k = 3;
    combinations(n, k);
    return 0;
}

Pascal (Pascal ABC)

pascalCopy code
program Combinations;

procedure CombinationsUtil(combination: array of Integer; n, k, start: Integer);
var
  i: Integer;
begin
  if k = 0 then
  begin
    // Выводим текущую комбинацию
    for i := Low(combination) to High(combination) do
      Write(combination[i], ' ');
    Writeln;
    Exit;
  end;

  // Генерируем сочетания рекурсивно
  for i := start to n - k + 1 do
  begin
    combination[High(combination) - k + 1] := i;
    CombinationsUtil(combination, n, k - 1, i + 1);
  end;
end;

procedure Combinations(n, k: Integer);
var
  combination: array of Integer;
begin
  SetLength(combination, k);
  CombinationsUtil(combination, n, k, 1);
end;

begin
  Combinations(5, 3);
end.

Python

pythonCopy code
def combinations_util(combination, n, k, start):
    if k == 0:
        # Выводим текущую комбинацию
        print(*combination)
        return

    # Генерируем сочетания рекурсивно
    for i in range(start, n - k + 2):
        combination.append(i)
        combinations_util(combination, n, k - 1, i + 1)
        combination.pop()

def combinations(n, k):
    combination = []
    combinations_util(combination, n, k, 1)

n = 5
k = 3
combinations(n, k)

В каждом из приведенных примеров функция combinations генерирует все сочетания из n-элементного множества по k и выводит их на экран. Например, при n=5 и k=3 результатом будет:

Copy code
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5