Алгоритм возврата всех комбинаций k элементов из n

Question

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

Допустим, вы предоставляете массив из 8 букв и хотите выбрать 3 буквы из этого. Тогда вы должны получить:

8! / ((8 - 3)! * 3!) = 56

Массивы (или слова) в ответ, состоящие из 3 букв.

Answer 1

Мы можем использовать понятие битов, чтобы сделать это. Пусть у нас есть строка «abc», и мы хотим иметь все комбинации элементов длиной 2 (т. Е. «Ab», «ac», «bc».)

Мы можем найти установленные биты в числах от 1 до 2 ^ n (исключая). Здесь с 1 по 7, и где бы мы ни установили биты = 2, мы можем вывести соответствующее значение из строки.

например:

• 1 - 001
• 2 - 010
• 3 - 011 -> print ab (str[0] , str[1])
• 4 - 100
• 5 - 101 -> print ac (str[0] , str[2])
• 6 - 110 -> print ab (str[1] , str[2])
• 7 - 111.

Пример кода:

public class StringCombinationK {   
    static void combk(String s , int k){
        int n = s.length();
        int num = 1<<n;
        int j=0;
        int count=0;

        for(int i=0;i<num;i++){
            if (countSet(i)==k){
                setBits(i,j,s);
                count++;
                System.out.println();
            }
        }

        System.out.println(count);
    }

    static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
        if(i==0){
            return;
        }

        if(i%2==1){
            System.out.print(s.charAt(j));                  
        }

        setBits(i/2,j+1,s);
    }

    static int countSet(int i){ //count number of set bits
        if( i==0){
            return 0;
        }

        return (i%2==0? 0:1) + countSet(i/2);
    }

    public static void main(String[] arhs){
        String s = "abcdefgh";
        int k=3;
        combk(s,k);
    }
}

Answer 2

В Python используются преимущества рекурсии и тот факт, что все делается по ссылке. Это займет много памяти для очень больших наборов, но имеет то преимущество, что начальный набор может быть сложным объектом. Он найдет только уникальные комбинации.

import copy

def find_combinations( length, set, combinations = None, candidate = None ):
    # recursive function to calculate all unique combinations of unique values
    # from [set], given combinations of [length].  The result is populated
    # into the 'combinations' list.
    #
    if combinations == None:
        combinations = []
    if candidate == None:
        candidate = []

    for item in set:
        if item in candidate:
            # this item already appears in the current combination somewhere.
            # skip it
            continue

        attempt = copy.deepcopy(candidate)
        attempt.append(item)
        # sorting the subset is what gives us completely unique combinations,
        # so that [1, 2, 3] and [1, 3, 2] will be treated as equals
        attempt.sort()

        if len(attempt) < length:
            # the current attempt at finding a new combination is still too
            # short, so add another item to the end of the set
            # yay recursion!
            find_combinations( length, set, combinations, attempt )
        else:
            # the current combination attempt is the right length.  If it
            # already appears in the list of found combinations then we'll
            # skip it.
            if attempt in combinations:
                continue
            else:
                # otherwise, we append it to the list of found combinations
                # and move on.
                combinations.append(attempt)
                continue
    return len(combinations)

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

size = 3
set = [1, 2, 3, 4, 5]
result = []

num = find_combinations( size, set, result ) 
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

Вы должны получить следующие выходные данные из этих тестовых данных:

size 3 results in 10 sets
result: [[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]]

И это будет работать так же хорошо, если ваш сет выглядит так:

set = [
    [ 'vanilla', 'cupcake' ],
    [ 'chocolate', 'pudding' ],
    [ 'vanilla', 'pudding' ],
    [ 'chocolate', 'cookie' ],
    [ 'mint', 'cookie' ]
]

Answer 3

Простой, но медленный алгоритм возврата C ++.

#include <iostream>

void backtrack(int* numbers, int n, int k, int i, int s)
{
    if (i == k)
    {
        for (int j = 0; j < k; ++j)
        {
            std::cout << numbers[j];
        }
        std::cout << std::endl;

        return;
    }

    if (s > n)
    {
        return;
    }

    numbers[i] = s;
    backtrack(numbers, n, k, i + 1, s + 1);
    backtrack(numbers, n, k, i, s + 1);
}

int main(int argc, char* argv[])
{
    int n = 5;
    int k = 3;

    int* numbers = new int[k];

    backtrack(numbers, n, k, 0, 1);

    delete[] numbers;

    return 0;
}

Answer 4

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

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Вы можете увидеть объяснение того, как это работает здесь .

Answer 5

C # простой алгоритм. (Я публикую его, так как я пытался использовать тот, который вы, ребята, загрузили, но по какой-то причине я не смог скомпилировать его - расширить класс? Я сделал). Кстати, я не сильно увлекаюсь C # больше, чем базовым программированием, но этот работает нормально.

public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
        {
            List<List<int>> lSubsets = new List<List<int>>();
            GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
            return lSubsets;
        }

public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
        {
            if (lCurrSet.Count == k)
            {
                lSubsets.Add(lCurrSet);
                return;
            }

            if (i >= lInputSet.Count)
                return;

            List<int> lWith = new List<int>(lCurrSet);
            List<int> lWithout = new List<int>(lCurrSet);
            lWith.Add(lInputSet[i++]);

            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
        }

ИСПОЛЬЗОВАНИЕ: GetSubsetsOfSizeK(set of type List<int>, integer k)

Вы можете изменить его, чтобы перебирать все, с чем вы работаете.

Удачи!

Answer 6

Вот решение C ++, которое я придумал, используя рекурсию и сдвиг битов. Может работать и в Си.

void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Вы можете найти объяснение того, как это работает здесь .

Answer 7

Моя реализация на с / с ++

#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int opt = -1, min_len = 0, max_len = 0;
    char ofile[256], fchar[2], tchar[2];
    ofile[0] = 0;
    fchar[0] = 0;
    tchar[0] = 0;
    while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
    {
            switch(opt)
            {
                    case 'o':
                    strncpy(ofile, optarg, 255);
                    break;
                    case 'f':
                    strncpy(fchar, optarg, 1);
                    break;
                    case 't':
                    strncpy(tchar, optarg, 1);
                    break;
                    case 'l':
                    min_len = atoi(optarg);
                    break;
                    case 'L':
                    max_len = atoi(optarg);
                    break;
                    default:
                    printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
            }
    }
if(max_len < 1)
{
    printf("error, length must be more than 0\n");
    return 1;
}
if(min_len > max_len)
{
    printf("error, max length must be greater or equal min_length\n");
    return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
    printf("error, invalid range specified\n");
    return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
    printf("failed to open input file with error: %s\n", strerror(errno));
    return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
    char buf[cur_len];
    for(int i = 0; i < cur_len; i++)
        buf[i] = fchar[0];
    fwrite(buf, cur_len, 1, out);
    fwrite("\n", 1, 1, out);
    while(buf[0] != (tchar[0]+1))
    {
        while(buf[cur_len-1] < tchar[0])
        {
            (int)buf[cur_len-1]++;
            fwrite(buf, cur_len, 1, out);
            fwrite("\n", 1, 1, out);
        }
        if(cur_len < 2)
            break;
        if(buf[0] == tchar[0])
        {
            bool stop = true;
            for(int i = 1; i < cur_len; i++)
            {
                if(buf[i] != tchar[0])
                {
                    stop = false;
                    break;
                }
            }
            if(stop)
                break;
        }
        int u = cur_len-2;
        for(; u>=0 && buf[u] >= tchar[0]; u--)
            ;
        (int)buf[u]++;
        for(int i = u+1; i < cur_len; i++)
            buf[i] = fchar[0];
        fwrite(buf, cur_len, 1, out);
        fwrite("\n", 1, 1, out);
    }
    cur_len++;
}
fclose(out);
return 0;
}

здесь моя реализация на c ++, она записывает все комбинации в указанные файлы, но поведение может быть изменено, я сделал для создания различных словарей, он принимает минимальную и максимальную длину и диапазон символов, в настоящее время поддерживается только ANSI, этого достаточно для моего необходимо

Answer 8

Короткая быстрая реализация C #

public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
    return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));                
}      

public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
    var result = new List<int[]>();

    var lastIndex = subSetLenght - 1;
    var dif = setLenght - subSetLenght;
    var prevSubSet = new int[subSetLenght];
    var lastSubSet = new int[subSetLenght];
    for (int i = 0; i < subSetLenght; i++)
    {
        prevSubSet[i] = i;
        lastSubSet[i] = i + dif;
    }

    while(true)
    {
        //add subSet ad result set
        var n = new int[subSetLenght];
        for (int i = 0; i < subSetLenght; i++)
            n[i] = prevSubSet[i];

        result.Add(n);

        if (prevSubSet[0] >= lastSubSet[0])
            break;

        //start at index 1 because index 0 is checked and breaking in the current loop
        int j = 1;
        for (; j < subSetLenght; j++)
        {
            if (prevSubSet[j] >= lastSubSet[j])
            {
                prevSubSet[j - 1]++;

                for (int p = j; p < subSetLenght; p++)
                    prevSubSet[p] = prevSubSet[p - 1] + 1;

                break;
            }
        }

        if (j > lastIndex)
            prevSubSet[lastIndex]++;
    }

    return result;
}

Answer 9

Это мой вклад в JavaScript (без рекурсии)

set = ["q0", "q1", "q2", "q3"]
collector = []


function comb(num) {
  results = []
  one_comb = []
  for (i = set.length - 1; i >= 0; --i) {
    tmp = Math.pow(2, i)
    quotient = parseInt(num / tmp)
    results.push(quotient)
    num = num % tmp
  }
  k = 0
  for (i = 0; i < results.length; ++i)
    if (results[i]) {
      ++k
      one_comb.push(set[i])
    }
  if (collector[k] == undefined)
    collector[k] = []
  collector[k].push(one_comb)
}


sum = 0
for (i = 0; i < set.length; ++i)
  sum += Math.pow(2, i)
 for (ii = sum; ii > 0; --ii)
  comb(ii)
 cnt = 0
for (i = 1; i < collector.length; ++i) {
  n = 0
  for (j = 0; j < collector[i].length; ++j)
    document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
  document.write("<hr>")
}   

Answer 10

Вот мое JavaScript-решение, которое немного более функционально благодаря использованию Reduce / Map, которая исключает почти все переменные

function combinations(arr, size) {
  var len = arr.length;

  if (size > len) return [];
  if (!size) return [[]];
  if (size == len) return [arr];

  return arr.reduce(function (acc, val, i) {
    var res = combinations(arr.slice(i + 1), size - 1)
      .map(function (comb) { return [val].concat(comb); });
    
    return acc.concat(res);
  }, []);
}

var combs = combinations([1,2,3,4,5,6,7,8],3);
combs.map(function (comb) {
  document.body.innerHTML += comb.toString() + '<br />';
});

document.body.innerHTML += '<br /> Total combinations = ' + combs.length;