комбинация без повторения N элементов без использования для .. to..do

Question

Я хочу загрузить в список комбинацию из N чисел без повторений, давая для ввода элементы и группы. Например, с 4 элементами [1,2,3,4] у меня есть для:

Group 1: [1][2][3][4]; 
Group 2: [1,2][1,3][1,4][2,3][2,4][3,4];
Group 3: [1,2,3][1,2,4][1,3,4][2,3,4]
Group 4: [1,2,3,4]

Теперь я решил это с помощью вложенного цикла, например, для группы 2, я пишу:

  for x1 := 1 to 3 do
    for x2 := Succ(x1) to 4 do
      begin
        // x1, x2 // 
      end

или для группы 3 я написал:

  for x1 := 1 to 2 do
    for x2 := Succ(x1) to 3 do
      for x3 := Succ(x2) to 4 do
      begin
        // x1, x2, x3 // 
      end

и так для других групп. В общем, если я хочу сделать это для группы N, как я могу сделать, без написания N процедур с вложенными циклами? Я подумал о двойном цикле while..do, чтобы использовать его для счетчика, а другой - для подсчета групп, но это не так сложно, я хотел знать, было ли какое-то решение более простым и быстрым, тоже с использованием логического оператора или что-то подобное , Кто может дать мне совет по этому поводу? Большое спасибо.

Answer 1

Кажется, вы ищете быстрый алгоритм для вычисления всех k-комбинаций.Следующий код Delphi является прямым переводом кода C, найденного здесь: Генерация комбинаций .Я даже исправил ошибку в этом коде!

program kCombinations;

{$APPTYPE CONSOLE}

// Prints out a combination like {1, 2}
procedure printc(const comb: array of Integer; k: Integer);
var
  i: Integer;
begin
    Write('{');
    for i := 0 to k-1 do
  begin
    Write(comb[i]+1);
    if i<k-1 then
      Write(',');
  end;
    Writeln('}');
end;

(*
Generates the next combination of n elements as k after comb
  comb => the previous combination ( use (0, 1, 2, ..., k) for first)
  k => the size of the subsets to generate
  n => the size of the original set

  Returns: True if a valid combination was found, False otherwise
*)
function next_comb(var comb: array of Integer; k, n: Integer): Boolean;
var
  i: Integer;
begin
    i := k - 1;
    inc(comb[i]);
    while (i>0) and (comb[i]>=n-k+1+i) do
  begin
    dec(i);
        inc(comb[i]);
    end;

    if comb[0]>n-k then// Combination (n-k, n-k+1, ..., n) reached
  begin
    // No more combinations can be generated
    Result := False;
    exit;
  end;

    // comb now looks like (..., x, n, n, n, ..., n).
    // Turn it into (..., x, x + 1, x + 2, ...)
    for i := i+1 to k-1 do
        comb[i] := comb[i-1]+1;

  Result := True;
end;

procedure Main;
const
    n = 4;// The size of the set; for {1, 2, 3, 4} it's 4
    k = 2;// The size of the subsets; for {1, 2}, {1, 3}, ... it's 2
var
  i: Integer;
  comb: array of Integer;
begin
  SetLength(comb, k);// comb[i] is the index of the i-th element in the combination

    //Setup comb for the initial combination
  for i := 0 to k-1 do
        comb[i] := i;

    // Print the first combination
    printc(comb, k);

    // Generate and print all the other combinations
    while next_comb(comb, k, n) do
        printc(comb, k);
end;

begin
  Main;
  Readln;
end.

Вывод

{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}

Answer 2

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

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

program VisitAllSubsetsDemo;

{$APPTYPE CONSOLE}

procedure PrintBitset(Bitset: Cardinal; Size: Integer);
var
  i: Integer;
  Mask: Cardinal;
  SepNeeded: Boolean;
begin
  SepNeeded := False;
  Write('{');
  for i := 1 to Size do begin
    Mask := 1 shl (i-1);
    if Bitset and Mask<>0 then begin
      if SepNeeded then begin
        Write(',');
      end;
      Write(i);
      SepNeeded := True;
    end;
  end;
  Writeln('}');
end;

procedure EnumerateSubsets(Size: Integer);
var
  Bitset: Cardinal;
begin
  for Bitset := 0 to (1 shl Size)-1 do begin
    PrintBitset(Bitset, Size);
  end;
end;

begin
  EnumerateSubsets(4);
end.

выход

{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
{4}
{1,4}
{2,4}
{1,2,4}
{3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}

А вот вариант, который просто перечисляет подмножества указанной мощности:

function SetBitCount(Bitset: Cardinal; Size: Integer): Integer;
var
  i: Integer;
  Mask: Cardinal;
begin
  Result := 0;
  for i := 1 to Size do begin
    Mask := 1 shl (i-1);
    if Bitset and Mask<>0 then begin
      inc(Result);
    end;
  end;
end;

procedure EnumerateSubsets(Size, NumberOfSetBits: Integer);
var
  Bitset: Cardinal;
begin
  for Bitset := 0 to (1 shl Size)-1 do begin
    if SetBitCount(Bitset, Size)=NumberOfSetBits then begin
      PrintBitset(Bitset, Size);
    end;
  end;
end;

begin
  EnumerateSubsets(4, 2);
end.

выход

{1,2}
{1,3}
{2,3}
{1,4}
{2,4}
{3,4}

Answer 3

Это, кажется, вопрос, который возникает снова и снова, и несколько бит кода пиная об этом, решай проблему. Очень хороший алгоритм в некотором коде был написано, но это был не совсем чистый C и не переносимый в UNIX или Linux или любой другой Система POSIX, поэтому я очистил ее и добавил предупреждающие сообщения, использование и Возможность указать размер набора и размер sub_set в командной строке. Также расческа [] имеет был переведен на более общий указатель на массив целых чисел и используется calloc обнулить память, необходимую для любого желаемого размера набора.

В соответствии с ISO IEC 9899: 1999 C clean:

/*********************************************************************
 * The Open Group Base Specifications Issue 6
 * IEEE Std 1003.1, 2004 Edition
 *
 *    An XSI-conforming application should ensure that the feature 
 *    test macro _XOPEN_SOURCE is defined with the value 600 before 
 *    inclusion of any header. This is needed to enable the 
 *    functionality described in The _POSIX_C_SOURCE Feature Test 
 *    Macro and in addition to enable the XSI extension.
 *
 * Compile with c99 or with gcc and CFLAGS to include options 
 * -std=iso9899:199409 -pedantic-errors in order to ensure compliance
 * with ISO IEC 9899:1999 C spec. 
 *
 * Code cleanup and transition to comb as a pointer to type ( int * ) 
 * array by Dennis Clarke dclarke@blastwave.org  28 Dec 2012 
 *
 *********************************************************************/
#define _XOPEN_SOURCE 600

#include <stdio.h>
#include <stdlib.h>

/* Prints out a combination like {1, 2} */
void printc( int *comb, int k) {

    int j;
    printf("{ ");

    for ( j = 0; j < k; ++j )
        printf("%d , ", *( comb + j ) + 1 );

    printf( "\b\b}\n" );

} /* printc */

/**********************************************************************
    next_comb(int comb[], int k, int n)
    Generates the next combination of n elements as k after comb

    comb => the previous combination ( use (0, 1, 2, ..., k) for first)
    k => the size of the subsets to generate
    n => the size of the original set

    Returns: 1 if a valid combination was found
    0, otherwise
**********************************************************************/

int next_comb( int *comb, int k, int n) {

    int i = k - 1;
    ++*( comb + i );
    while ( ( i >= 0 ) && ( *( comb + i ) >= n - k + 1 + i ) ) {
        --i;
        ++*( comb + i );
    }

    if ( *comb > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
        return 0; /* No more combinations can be generated */

    /* comb now looks like (..., x, n, n, n, ..., n).
     * Turn it into (..., x, x + 1, x + 2, ...) */
    for (i = i + 1; i < k; ++i)
        *( comb + i ) = *( comb + ( i - 1 ) ) + 1;

    return 1;

} /* next_comb */

int main(int argc, char *argv[]) {

    int *comb, i, n, k;

    n = 9; /* The size of the set; for {1, 2, 3, 4} it's 4 */
    k = 6; /* The size of the subsets; for {1, 2}, {1, 3}, .. it's 2 */

    if ( argc < 3 ) { 
        printf ( "\nUSAGE : %s n k\n", argv[0] );
        printf ( "      : Where n is the set size and k the sub set size.\n" );
        printf ( "      : Note that k <= n\n" );
        return ( EXIT_FAILURE );
    }

    n = atoi ( argv[1] );
    k = atoi ( argv[2] );

    if ( k > n ) {
        printf ( "\nWARN  : k > n is not allowed.\n" );
        printf ( "USAGE : %s n k\n", argv[0] );
        printf ( "      : Where n is the set size and k the sub set size.\n" );
        printf ( "      : Note that k <= n\n" );
        return ( EXIT_FAILURE );
    }

    comb = ( int * ) calloc( (size_t) k, sizeof(int) );

    for ( i = 0; i < k; ++i)
        *( comb + i ) = i;

    /* Print the first combination */
    printc( comb, k );

    /* Generate and print all the other combinations */
    while ( next_comb( comb, k, n ) )
        printc( comb, k );

    free ( comb );

    return ( EXIT_SUCCESS );

}

Можно скомпилировать вышесказанное на машине Opteron следующим образом:

$ echo $CFLAGS 
-m64 -g -malign-double -std=iso9899:199409 -pedantic-errors -mno-mmx 
-mno-sse -fexceptions -fpic -fvisibility=default -mtune=opteron 
-march=opteron -m128bit-long-double -mpc80 -Wl,-q
$ gcc $CFLAGS -o combinations combinations.c 

Быстрый тривиальный тест с размером набора 10 и подмножеством 6 будет таким:

$ ./combinations 10 6 | wc -l 
210

Математика верна:

 ( 10 ! ) / ( ( 10 - 6 )!  *  ( 6! ) )  =   210 unique combinations. 

Теперь, когда гребень целочисленного массива основан на системе указателей, мы ограничены только по доступной памяти и времени. Поэтому имеем следующее:

$ /usr/bin/time -p ./combinations 20 6 | wc -l 
real 0.11
user 0.10
sys 0.00
38760

Это выглядит правильно:

( 20 ! ) / ( ( 20 - 6 )!  *  ( 6! ) )  = 38,760 unique combinations

Теперь мы можем немного расширить границы:

$ ./combinations 30 24 | wc -l 
593775

Снова математика соглашается с результатом:

( 30 ! ) / ( ( 30 - 24 )!  *  ( 24! ) )  =  593 775 unique combinations

Не стесняйтесь расширять границы вашей системы:

$ /usr/bin/time -p ./combinations 30 22 | wc -l  
real 18.62
user 17.76
sys 0.83
5852925

Мне еще предстоит попробовать что-то большее, но математика выглядит правильно, как и результат до сих пор. Не стесняйтесь, дайте мне знать, если некоторая коррекция необходима.

Деннис Кларк dclarke@blastwave.org 28 декабря 2012

Answer 4

Я создал этот скрипт здесь и работал очень хорошо:

$(document).ready(function(){
    $("#search").on('click', function(){
        var value = $("#fieldArray").val().split(",");
        var results = new SearchCombinations(value);
        var output = "";
        for(var $i = 0; $i< results.length;$i++){
        	results[$i] = results[$i].join(",");
            output +="<li>"+results[$i]+"</li>";
        }
        $("#list").html(output);
    });
});

/*Helper Clone*/
var Clone = function (data) {
    return JSON.parse(JSON.stringify(data));
}

/*Script of Search All Combinations without repetitions. Ex: [1,2,3]*/
var SearchCombinations = function (statesArray) {
    var combinations = new Array(),
        newValue = null,
        arrayBeforeLevel = new Array(),
        $level = 0,
        array = new Clone(statesArray),
        firstInteration = true,
        indexFirstInteration = 0,
        sizeValues = array.length,
        totalSizeValues = Math.pow(2, array.length) - 1;
    array.sort();
    combinations = new Clone(array);
    arrayBeforeLevel = new Clone(array);
    loopLevel: while ($level < arrayBeforeLevel.length) {
        for (var $i = 0; $i < array.length; $i++) {
            newValue = arrayBeforeLevel[$level] + "," + array[$i];
            newValue = newValue.split(",");
            newValue.sort();
            newValue = newValue.join(",");
            if (combinations.indexOf(newValue) == -1 && arrayBeforeLevel[$level].toString().indexOf(array[$i]) == -1) {
                if (firstInteration) {
                    firstInteration = false;
                    indexFirstInteration = combinations.length
                }
                sizeValues++;
                combinations.push(newValue);
                if (sizeValues == totalSizeValues) {
                    break loopLevel;
                }
            }
        }
        $level++;
        if ($level == arrayBeforeLevel.length) {
            firstInteration = true;
            arrayBeforeLevel = new Clone(combinations);
            arrayBeforeLevel = arrayBeforeLevel.splice(indexFirstInteration);
            indexFirstInteration = 0;
            $level = 0;
        }
    }
    for (var $i = 0; $i < combinations.length; $i++) {
        combinations[$i] = combinations[$i].toString().split(",");
    }
    return combinations;
}

*{font-family: Arial;font-size:14px;}
small{font-size:11px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<label for="">
    <input type="text" id="fieldArray">
    <button id="search">Search</button>
    <br><small>Info the elements. Ex: "a,b,c"</small>
</label>
<hr>
<ul id="list"></ul>

Answer 5

Перейдя по ссылке, которую Дэвид разместил и щелкнув по ней, я перешел к статье, в которой появился термин «Поиск банкира», который, кажется, соответствует вашему шаблону.

В статье приведен пример решения на C ++ с использованием рекурсии:

Эффективное перечисление подмножеств набора

Answer 6

Если вы не можете выполнять вызовы функций по каким-либо требованиям, сделайте следующее:

select_n_from_list(int *selected, int n, int *list, int list_size):
    if (n==0) {
        // print all numbers from selected by traversing backward
        // you can set the head to a special value or make the head location
        // a static variable for lookup
    }

    for (int i=0; i<=list_size-n; i++) {
        *selected = list[i];
        select_n_from_list(selected+1, n-1, list+i+1, list_size-i-1);
    }
}

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