我想要获得所有可能的char*组合。该字符串由四个值组成：两个数字和两个不同的字母。例如：
char *text = "01ab";
应该有
所以
我的示例字符串的不同组合，似乎是真的（手工完成）：
Combinations for values: 0, 1, a, b:
0 0 a b 1 1 a b a 0 0 b b 0 0 a
0 0 b a 1 1 b a a 0 1 b b 0 1 a
0 1 a b 1 0 a b a 0 b 0 b 0 a 0
0 1 b a 1 0 b a a 0 b 1 b 0 a 1
0 a 0 b 1 a 1 b a 1 b 0 b 1 0 a
0 a 1 b 1 a 0 b a 1 b 1 b 1 1 a
0 a b 0 1 a b 1 a 1 0 b b 1 a 0
0 a b 1 1 a b 0 a 1 1 b b 1 a 1
0 b 0 a 1 b 1 a a b 0 0 b a 0 0
0 b 1 a 1 b 0 a a b 0 1 b a 0 1
0 b a 0 1 b a 1 a b 1 0 b a 1 0
0 b a 1 1 b a 0 a b 0 0 b a 1 1
我的方法与我手工完成的方法相同：在开始时获得text的第一个索引的所有组合，然后是text的第二个索引的所有组合，依此类推。所以像这样：
void printPasswordCombinations()
{
char *all_values = "01ab";
int len = strlen(all_values);
char *tmp_pwd = malloc(sizeof(len) * sizeof(char));
for(int i=0 ; i<len ; i++)
{
tmp_pwd[0] = all_values[i];
/* len-1, since the first index is already set. */
for(int j=0 ; j<len-1 ; j++)
{
}
}
printf("%s\n", tmp_pwd);
free(tmp_pwd);
}
现在我对如何在组合的第一个索引之后继续感到困惑。所有组合都有several examples，但我的问题似乎有点不同，因为我的组合中的数字可能是相同的，只有字母必须不同。
如何将所有组合打印到我的控制台？我实现了一个计算可能组合数量的函数，所以假设已经完成了。
如果算法可以适用于任何数量的numbers和letters，那将是很好的，所以例如lenght 6与four different numbers和两个different letters的文本的所有组合也可以计算。
语言无关紧要，任何建议都表示赞赏。
我使用Javascript是因为它可以在浏览器中运行并且语言无关紧要。以下方法使用递归。尝试使用'0123ab'。
'use strict';
const input = '01ab';
const reLetters = /[^0-9]/g;
const reDigits = /[0-9]/g;
const nLetters = input.replace(reDigits, '').length;
const nDigits = input.replace(reLetters, '').length;
const findComb = cur => {
if (cur.length === input.length)
return console.log(cur);
for (let l of input) {
if (l.match(reDigits)) {
if (cur.replace(reLetters, '').length === nDigits) continue;
} else {
if (cur.match(l) || cur.replace(reDigits, '').length === nLetters) continue;
}
findComb(cur + l);
}
}
findComb('');这是一个没有“删除字母计数位数”的版本。它的效率提高了约20％。我使用nodejs和'01234abc'作为测量的输入。
'use strict';
const input = '01ab';
const reLetters = /[^0-9]/g;
const reDigits = /[0-9]/g;
const maxLetters = input.replace(reDigits, '').length;
const maxDigits = input.replace(reLetters, '').length;
const findComb = (cur = '', nDigits = 0, nLetters = 0) => {
if (cur.length === input.length)
return console.log(cur);
for (let l of input) {
if (l.match(reDigits)) {
if (nDigits < maxDigits)
findComb(cur + l, nDigits + 1, nLetters);
} else {
if (cur.match(l)) continue;
if (nLetters < maxLetters)
findComb(cur + l, nDigits, nLetters + 1);
}
}
}
findComb();这里没有递归。这是最慢的，但可以改进。
'use strict';
const input = '01ab';
const reLetters = /[^0-9]/g;
const reDigits = /[0-9]/g;
const nLetters = input.replace(reDigits, '').length;
const nDigits = input.replace(reLetters, '').length;
let cur = '', l = undefined;
do {
l = input[input.indexOf(l) + 1];
if (l !== undefined) {
if (l.match(reDigits)) {
if (cur.replace(reLetters, '').length === nDigits) continue;
} else {
if (cur.match(l) ||
cur.replace(reDigits, '').length === nLetters) continue;
}
if (cur.length + 1 === input.length) {
console.log(cur + l);
} else {
cur = cur + l;
l = undefined;
}
} else {
l = cur[cur.length - 1];
cur = cur.slice(0, -1);
}
} while (cur != '' || l != undefined);你的问题可以通过回溯策略来解决。它将创建所有可能的组合。
我知道你要删除重复的组合，以防两个数字相同，为了摆脱它们，你可以使用哈希表来存储生成的组合，然后，每次你生成一个新的组合，把它带到哈希用于检查是否生成的表（如果没有，请将其输入哈希表并将其打印出来，忽略打印，反之亦然）。我的伪代码如下（你可以有更好的方法）：
val characters = [/*4 characters*/]
val picked = [false,false,false,false]
val hashtable = empty
function genetate(string aCombin):
if aCombin.size == 4:
if(hashtable.contains(aCombin)):
//do nothing
else:
print(aCombin)
hashtable.add(aCombin)
for i in characters.size:
if(picked[i]==false):
picked[i]=true
aCombin.add(characters[i])
generate(aCombin)
picked[i]=false //backtrack
aCombine.popBack() //remove the last character
递归方法将是这里的简单方法。
让我们考虑你想要生成m字母的所有字符串，所有字母都是不同的，取自letters[m]数组，n数字，可以重复，取自numbers[N]数组（n可以更小，大小相同） N，它并不重要）。
你可以这样解决它（伪代码，C风格）：
void print_them_all(char *numbers, int nb_numbers_in_result, int n \
char *letters, bool *is_letter_used, int nb_letters_in_result, int m,
char *current_string){
if ((nb_numbers_in_result == n) && (nb_letters_in_result == m)){
// terminal case -> time to print the current string
printf("%s\n", current_string);
} else {
// string not completely built yet
// get the index where the next char will be added
current_index = nb_letters_in_result + nb_numbers_in_result;
if (nb_numbers_in_result < n){ // still possible to add a number
for (int i = 0; i < N; i++){
current_string[current_index] = numbers[i];
print_them_all(numbers, nb_numbers_in_result+1, n, \
letters, is_letter_used, nb_letters_in_result, m, \
current_string);
}
}
if (nb_letters_in_result < m){ // still possible to add a letter
for (int i = 0; i < m; i++) {
if (is_letter_used[i] == false){ // check the letter has not been added yet
// keep track that the letter has been added by 'marking' it
is_letter_used[i] = true;
// add it
current_string[i] = letters[i];
// recursive call
print_them_all(numbers, nb_numbers_in_result, n, \
letters, is_letter_used, nb_letters_in_result+1, m, \
current_string);
// now 'unmark' the letter
is_letter_used[i] = false;
}
}
}
}
}
要解决这类问题，递归方法是必要的。它的工作原理如下：
如果我已经有一个k数字的字符串，k<n，那么我可以添加任何数字，我可以继续（现在我的字符串将有k+1数字）。
如果我已经有一个k字母的字符串，k<m，那么我可以添加任何尚未添加的字母（布尔数组有助于确保它是这种情况），我可以继续。如果我的字符串已准备好打印，请将其打印出来。
第一次调用应该使用在任何地方初始化为false的布尔数组来完成，并且0用于nb_letters_in_result和nb_numbers_in_result的值，因为您还没有在结果字符串中添加任何数字或字母。
至于你的结果字符串，因为你用C编码，不要忘记为它分配内存：
char *current_string = malloc((m+n+1) * sizeof(char));
并将其终止：
current_string[m+n] = '\0';
我也为我的问题找到了一个有趣的解决方案。假设我的示例字符串01ab。
首先，我们要创建数字01和ab的排列的所有组合。有很多例子可以解决这个问题。
所以现在我们有01和ab的所有组合。我会称他们为制作人组合：
10 ab
01 ba
11
00
现在我们想要将所有数字与所有字母组合在一起，但要遵守规则
不得为每个组合保留数字或字母的顺序
因此，如果我们将10与ab结合起来，我们得到：
10ab
1a0b
a10b
现在我们将b移到左侧，直到它将要与a交换它的地方，因为我的统治是禁止的。我们为每个组合做到这一点：
10ab produces:
10ab
因为b已经在a了。
1a0b produces:
1ab0
所以我们又有了一个组合。
a10b produces:
a1b0
ab10
所以我们还有2个组合。
现在我们为01 and ab提供了所有可能的组合：
10ab
1a0b
a10b
1ab0
a1b0
ab10
由于我们的生产者组合包含8个元素，我们必须使用所有元素执行此步骤8次。结果组合总是包含6个元素，就像在我的例子中一样，这导致我们在我的问题中计算出总数为48的元素。