我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。

假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:

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

数组(或单词),每个数组由3个字母组成。


当前回答

在c++中,以下例程将生成range [first,last)之间的长度距离(first,k)的所有组合:

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

它可以这样使用:

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

这将打印以下内容:

123
124
125
134
135
145
234
235
245
345

其他回答

像Andrea Ambu一样用Python写的,但不是硬编码来选择三个。

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            print [list[index] for index in seq]
            seq = get_next_combination(len(list), k, seq)

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1

            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1

            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None   

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)

您可以修改它以遍历您正在处理的任何内容。

好运!

现在又出现了祖辈COBOL,一种饱受诟病的语言。

让我们假设一个包含34个元素的数组,每个元素8个字节(完全是任意选择)。其思想是枚举所有可能的4元素组合,并将它们加载到一个数组中。

我们使用4个指标,每个指标代表4个组中的每个位置

数组是这样处理的:

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

我们把idx4从4变到最后。对于每个idx4,我们得到一个唯一的组合 四人一组。当idx4到达数组的末尾时,我们将idx3增加1,并将idx4设置为idx3+1。然后再次运行idx4到最后。我们以这种方式继续,分别增加idx3、idx2和idx1,直到idx1的位置距离数组末端小于4。算法就完成了。

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

第一次迭代:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

一个COBOL的例子:

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

这是我对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>")
}   

我有一个用于project euler的排列算法,用python编写:

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

If

n<len(l) 

你应该有所有你需要的组合,没有重复,你需要吗?

它是一个生成器,所以你可以这样使用它:

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb