更新：これは、繰り返しのない組み合わせの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']
これは、目的の組み合わせのランクを生成し、次にランクから組み合わせを生成し、それを使用して選択肢のリストにインデックスを付けることによって機能します。そうすることで、インデックスの均等な分散が保証されます（したがって、他の組み合わせよりも頻繁に1つの組み合わせを生成することはありません）。
たとえば、10個のリストから5個の要素を選択したい場合、10 C 5=252可能な組み合わせがあります。最初の組み合わせは(0, 1, 2, 3, 4)、2番目は(0, 1, 2, 3, 5)、3番目は(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までの数値を一律に選択し、組み合わせを取得して、選択肢リストにインデックスを付ければ、完了です。
これは、組み合わせではなく、順列を生成した古いバージョンです。
1つの組み合わせを生成する方法は次のとおりです。
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])
最初に、可能な順列の数が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);
}