从给定的字符具有独特的组合 [英] making unique combinations from the given characters

问题描述

有没有一个适合这一个任何算法：

Is there any algorithm available for this one :

这是一组类似的字符：

a,@,n,M,O,f,D,),`,~,;,N,*,8,2,],2........ goes one . There are about 92 characters

现在我必须做出独特的组合，从一定长度的这92个字符（可能是5,3,2,10）的，直到满足某个条件。

Now I have to make unique combinations from these 92 characters of certain length (could be 5,3,2,10) until a certain condition is met.

就像从92 3个字符的组合可能是这样的：

Like a combination of 3 characters from 92 could be like :

abc
@82
)~N
......

对此有任何可用的算法或我有设备我自己的算法？

Is there any algorithm available for this or I have device my own algorithm?

推荐答案

更​​新：这是组合的工作Python版本没有重复：

UPDATE: Here is a working python version of combinations without repetitions:

def ncombs(n,k):
    if n < 0 or k < 0 or k > n: return 0
    b = 1
    for i in xrange(k): b = b*(n-i)/(i+1)
    return b

def nthresh(k, idx):
    """Finds the largest value m such that C(m, k) <= idx."""
    mk = k
    while ncombs(mk, k) <= idx:
        mk += 1
    return mk - 1

def rank_to_comb(k, rank):
    ret = []
    for i in range(k, 0, -1):
        element = nthresh(i, rank)
        ret.insert(0, element)
        rank -= ncombs(element, i)
    return ret

def random_combination(choices, n):
    num_combinations = ncombs(len(choices), n)
    desired_rank = random.randint(0, num_combinations-1)
    indices = idx_to_set(n, desired_rank)
    return [choices[i] for i in indices]

使用范例：

>>> random_combination("abcdefghijkl", 3)
['b', 'd', 'h']
>>> random_combination("abcdefghijkl", 3)
['b', 'd', 'g']
>>> random_combination("abcdefghijkl", 3)
['d', 'f', 'i']
>>> random_combination("abcdefghijkl", 3)
['d', 'f', 'h']
>>> random_combination("abcdefghijkl", 3)
['b', 'c', 'e']
>>> random_combination("abcdefghijkl", 3)
['c', 'i', 'l']
>>> random_combination("abcdefghijkl", 3)
['c', 'g', 'j']
>>> random_combination("abcdefghijkl", 3)
['b', 'j', 'l']

它的工作原理产生所需组合的等级，然后生成自合并等级，然后使用该索引到的选项列表。通过这样做，你保证均匀分布指数（这样你就不会产生任何一种组合往往比其他人）。

It works by generating the rank of the desired combination, then generating the combination from the rank, then using that to index into the list of choices. By doing so you guarantee an even distribution of indices (so you don't generate any one combination more often than others).

例如，如果你想从10列表中选择5个元素，有 10℃5 = 252 可能的组合。第一组合是（0，1，2，3，4）中，第二是（0，1，2，3，5），第三个是（0，1，2，4，5），等... rank_to_comb 函数来完成翻译：

For example, if you wanted to choose 5 elements from a list of 10, there are 10 C 5 = 252 possible combinations. The first combination is (0, 1, 2, 3, 4), the second is (0, 1, 2, 3, 5), the third is (0, 1, 2, 4, 5), etc... The rank_to_comb function accomplishes the translation:

>>> rank_to_comb(5, 0)
[0, 1, 2, 3, 4]
>>> rank_to_comb(5, 1)
[0, 1, 2, 3, 5]
>>> rank_to_comb(5, 2)
[0, 1, 2, 4, 5]
>>> rank_to_comb(5, 250)
[4, 6, 7, 8, 9]
>>> rank_to_comb(5, 251)
[5, 6, 7, 8, 9]

所以，我们只是从统一0挑选一个号码251，得到的结合，索引的选择列表中，我们就大功告成了！

So we just uniformly pick a number from 0 to 251, get the combination, index into the choices list, and we're done!

这是生成排列，而不是组合的旧版本：

This is the old version that generated permutations, not combinations:

下面是如何产生的一个组合：

Here is how to generate one combination:

public static String comboFrom(String possibleChars, int charsToTake) {
    //randomly shuffle the chars using Collections.shuffle
    List<Character> chars = new ArrayList<Character>(possibleChars.length());
    for (char c : possibleChars.toCharArray()) {
        chars.add(new Character(c));
    }

    Collections.shuffle(chars);

    //Take the first 'charsToTake' characters - these will be totally random
    //thanks to the shuffle
    String result = ""; 
    int taken=0;
    for (Character c : chars) {
        result += c.charValue();
        if (taken >= charsToTake) break;
        taken += 1;
    }
    return result;
}

使用范例：

for (int i=0; i < 30; i++) {
    System.out.println(comboFrom("abcdefghijkl@#%", 5));
}

了：

ecjlaf
bi@hfj
ia@#e%
icfad@
kb#gei
ik%@de
ib%jkf
flgb@#
gd@ekc
jedhi#
f@%ckj
lig%#j
l%fki#
ajgdlc
adkbe@
gb@cid
#efcag
@lihkc
k@j%#c
cgkaji
ecb@hj
k@lf%a
gd%fbh
c%lajf
e@#cid
%gfeb#
#%ahcf
be@flj
albjk@
calh%g

您只需反复调用此函数，当你得到一个结果，满足您的需求停止。这里是满code我用。

You can just call this function repeatedly and stop when you get a result that satisfies your needs. Here is the full code I used.

编辑：很遗憾这个插件，但是，这是这么多讨厌做的比我还以为我很高兴，我使用Python我的工作：

And sorry for this plug but this was so much more annoying to do than I thought that I'm glad I'm using Python at my job:

import random
def comboFrom(possibleChars, charsToTake):
    chars = list(possibleChars)
    random.shuffle(chars)
    return "".join(chars[:charsToTake])

这篇关于从给定的字符具有独特的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！