是否有任何可用的算法：
来自一组字符，例如：
a,@,n,M,O,f,D,),`,~,;,N,*,8,2,],2........ goes one . There are about 92 characters
现在我必须从这 92 个特定长度的字符（可能是 5、3、2、10）中进行独特的组合，直到满足特定条件。
就像来自 92 的 3 个字符的组合可能像：
abc
@82
)~N
......
有没有可用的算法或者我有自己的算法？
问问题
1997 次
2 回答
0
首先请注意，可能的排列数量在O(n^k)（Choose(n,k) = n!/(k!*(n-k)!)准确地说）其中n是字符数并且k是所需长度。由于它是指数级的，因此很容易变得遥不可及。
实现这些组合的一般算法是使用递归并探索直到这个长度的所有可能性。在每个级别，您“猜测”下一个将使用哪个字符，放置它，将其从可用字符列表中删除并递归解决较小的问题（查找排列到length-1）。
private static void printPermutations(char[] chars, int idx, List<Character> candidate, int length) {
if (length == candidate.size()) {
System.out.println(candidate);
return;
}
for (int i = idx; i < chars.length; i++) {
candidate.add(chars[i]);
//set the selected element out of reach:
char temp = chars[idx];
chars[idx] = chars[i];
chars[i] = temp;
//recurse:
printPermutations(chars, idx+1, candidate, length);
//clean up environment:
temp = chars[i];
chars[i] = chars[idx];
chars[idx] = temp;
candidate.remove(candidate.size()-1);
}
}
public static void printPermutations(char[] chars, int length) {
printPermutations(chars, 0, new LinkedList<Character>(), length);
}
于 2012-09-05T06:27:41.123 回答
0
更新：这是一个没有重复的组合的工作python版本：
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']
它的工作原理是生成所需组合的排名，然后从排名生成组合，然后使用它来索引选择列表。通过这样做，您可以保证索引的均匀分布（因此您不会比其他组合更频繁地生成任何一种组合）。
例如，如果您想从 10 个列表中选择 5 个元素，则有10 C 5=252可能的组合。第一个组合是(0, 1, 2, 3, 4)，第二个是(0, 1, 2, 3, 5)，第三个是(0, 1, 2, 4, 5)，等等……rank_to_comb函数完成翻译：
>>> 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 中选择一个数字，得到组合，索引到选择列表中，我们就完成了！
这是生成排列而不是组合的旧版本：
以下是如何生成一种组合：
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
您可以重复调用此函数并在获得满足您需求的结果时停止。这是我使用的完整代码。
编辑：对这个插件感到抱歉，但这比我想象的要烦人得多，我很高兴我在工作中使用了 Python：
import random
def comboFrom(possibleChars, charsToTake):
chars = list(possibleChars)
random.shuffle(chars)
return "".join(chars[:charsToTake])
于 2012-09-06T02:57:54.983 回答