扩展 C 蛮力算法
Extending C Brute Force Algorithm
我需要一个针对字母数字字符的蛮力算法。
我使用的代码只是将所有排列打印到标准输出。我尝试了几个小时,但未能以这样一种方式重写代码,即我可以在需要时调用函数 brute_next()
来获取下一个代码字。
有人可以帮我重写这段代码吗?函数 brute_next()
应该 return 一个 char*
或者获取一个 char*
作为参数。我在 Mac.
下将 CLion 与 gcc 一起使用
代码为(source):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";
static const int alphabetSize = sizeof(alphabet) - 1;
void bruteImpl(char* str, int index, int maxDepth)
{
for (int i = 0; i < alphabetSize; ++i)
{
str[index] = alphabet[i];
if (index == maxDepth - 1) printf("%s\n", str);
else bruteImpl(str, index + 1, maxDepth);
}
}
void bruteSequential(int maxLen)
{
char* buf = malloc(maxLen + 1);
for (int i = 1; i <= maxLen; ++i)
{
memset(buf, 0, maxLen + 1);
bruteImpl(buf, 0, i);
}
free(buf);
}
int main(void)
{
bruteSequential(3);
return 0;
}
这是我将递归转换为生成器的无效尝试。只是想不通排列算法是如何工作的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789"
"$%&/()=.-_;!+*#";
static const int alphabetSize = sizeof(alphabet) - 1;
struct bruteconfig {
int index;
int i1;
int i2;
char* str;
int maxDepth;
};
static struct bruteconfig* config;
void brute_init(int maxLen){
free(config);
config = malloc(sizeof(struct bruteconfig*));
config->i1 = 1;
config->i2 = 0;
config->index = 0;
config->maxDepth = maxLen;
}
void bruteImpl()
{
if(config->i2 > alphabetSize) // how to transform for to iterative?
config->i2 = 0;
config->str[config->index] = alphabet[config->i2];
if (config->index == config->maxDepth - 1) {
//printf("%s\n", config->str);
return; // str filled with next perm
}
else {
config->index++;
//bruteImpl(config->str, config->maxDepth);
}
config->i2++;
}
char* bruteSequential()
{
config->str = malloc(config->maxDepth + 1);
if(config->i1 >= config->maxDepth)
return NULL;
memset(config->str, 0, config->maxDepth + 1); // clear buf
bruteImpl(config->str, config->i1); // fill with next perm
return config->str;
//free(buf); // needs to be done by the caller
}
您正在尝试从递归切换到使用生成器:关键区别在于递归将工作状态隐式存储在调用堆栈中,而生成器需要为下一次调用显式存储其所有状态。
因此,首先您需要考虑在递归版本中为您隐式保留的状态:
- 递归调用的每个级别都有自己的参数值
index
- 每个级别都有自己的局部变量值
i
- ...就是这样。
您有 maxDepth
个级别,编号为 0..maxDepth-1
,每个级别在字母表中都有自己的当前位置。注意index
参数也只是这个集合中的位置,所以不需要单独存储。
现在,您需要在调用之间存储一些持久状态,这将是这个 maxDepth
整数字母表位置的数组。你能想出如何编写一个函数来将该数组转换为字符串吗?你能想出如何以与你的递归代码相同的方式将状态推进一位吗?
编辑 你的状态应该类似于
struct PermutationState {
/* stringLength == maxDepth */
int stringLength;
char *string;
/* better to avoid globals */
int alphaLength;
const char *alphabet;
/* this replaces i as the index into our alphabet */
int *alphaPos;
};
我建议写一个像
这样的界面
struct PermutationState* start_permutation(int stringLength,
int alphaLength,
const char *alphabet)
{
struct PermutationState *state = malloc(sizeof(*state));
if (!state) return NULL;
/* initialize scalar values first, for easier error-handling */
state->stringLength = stringLength;
state->string = NULL;
state->alphaLength = alphaLength;
state->alphabet = alphabet;
state->alphaPos = NULL;
/* now we can handle nested allocations */
state->string = malloc(stringLength + 1);
state->alphaPos = calloc(stringLength, sizeof(int));
if (state->string && state->alphaPos) {
/* both allocations succeeded, and alphaPos is already zeroed */
memset(state->string, alphabet[0], stringLength);
state->string[stringLength] = 0;
return state;
}
/* one or both of the nested allocations failed */
end_permutation(state);
return NULL;
}
void end_permutation(struct PermutationState *state)
{
free(state->string);
free(state->alphaPos);
free(state);
}
最后你要实现这个功能:
char *next_permutation(struct PermutationState *state)
{
/* TODO */
}
由于 start_permutation
已经为您设置了 state->alphaPos = [0, 0, ... 0]
和 state->string = "aaa...a"
,您可能希望将 alphaPos
提高一个位置,然后 return当前字符串。
注意。我假设您不需要复制字母表,这意味着调用者负责保证其生命周期。如有必要,您也可以轻松复制它。
I just can't figure out how the permutation algorithm works
非常简单:要从一个单词转到下一个单词,从最右边的位置开始,将该字符更改为字母表中的下一个;如果没有下一个字符,则将位置重置为字母表中的第一个字符,然后继续向左更改位置;如果没有剩余位置,则需要加长码字。这是一个示例实现:
char *brute_next()
{
for (; ; )
{
static char *buf; // buffer for codeword
static int maxDepth; // length of codeword
int i, index = maxDepth-1; // alphabet and buffer index, resp.
while (0 <= index) // as long as current length suffices:
{ // next char at buf[index] is next in alphabet or first:
i = buf[index] ? strchr(alphabet, buf[index]) - alphabet + 1 : 0;
if (buf[index] = alphabet[i]) return buf;
buf[index--] = alphabet[0]; // reset to 'a', continue to the left
}
index = maxDepth++; // now need to lengthen the codeword
buf = realloc(buf, maxDepth+1); // string length + terminator
if (!buf) exit(1);
buf[index] = buf[maxDepth] = '[=10=]';
}
}
我需要一个针对字母数字字符的蛮力算法。
我使用的代码只是将所有排列打印到标准输出。我尝试了几个小时,但未能以这样一种方式重写代码,即我可以在需要时调用函数 brute_next()
来获取下一个代码字。
有人可以帮我重写这段代码吗?函数 brute_next()
应该 return 一个 char*
或者获取一个 char*
作为参数。我在 Mac.
代码为(source):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";
static const int alphabetSize = sizeof(alphabet) - 1;
void bruteImpl(char* str, int index, int maxDepth)
{
for (int i = 0; i < alphabetSize; ++i)
{
str[index] = alphabet[i];
if (index == maxDepth - 1) printf("%s\n", str);
else bruteImpl(str, index + 1, maxDepth);
}
}
void bruteSequential(int maxLen)
{
char* buf = malloc(maxLen + 1);
for (int i = 1; i <= maxLen; ++i)
{
memset(buf, 0, maxLen + 1);
bruteImpl(buf, 0, i);
}
free(buf);
}
int main(void)
{
bruteSequential(3);
return 0;
}
这是我将递归转换为生成器的无效尝试。只是想不通排列算法是如何工作的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789"
"$%&/()=.-_;!+*#";
static const int alphabetSize = sizeof(alphabet) - 1;
struct bruteconfig {
int index;
int i1;
int i2;
char* str;
int maxDepth;
};
static struct bruteconfig* config;
void brute_init(int maxLen){
free(config);
config = malloc(sizeof(struct bruteconfig*));
config->i1 = 1;
config->i2 = 0;
config->index = 0;
config->maxDepth = maxLen;
}
void bruteImpl()
{
if(config->i2 > alphabetSize) // how to transform for to iterative?
config->i2 = 0;
config->str[config->index] = alphabet[config->i2];
if (config->index == config->maxDepth - 1) {
//printf("%s\n", config->str);
return; // str filled with next perm
}
else {
config->index++;
//bruteImpl(config->str, config->maxDepth);
}
config->i2++;
}
char* bruteSequential()
{
config->str = malloc(config->maxDepth + 1);
if(config->i1 >= config->maxDepth)
return NULL;
memset(config->str, 0, config->maxDepth + 1); // clear buf
bruteImpl(config->str, config->i1); // fill with next perm
return config->str;
//free(buf); // needs to be done by the caller
}
您正在尝试从递归切换到使用生成器:关键区别在于递归将工作状态隐式存储在调用堆栈中,而生成器需要为下一次调用显式存储其所有状态。
因此,首先您需要考虑在递归版本中为您隐式保留的状态:
- 递归调用的每个级别都有自己的参数值
index
- 每个级别都有自己的局部变量值
i
- ...就是这样。
您有 maxDepth
个级别,编号为 0..maxDepth-1
,每个级别在字母表中都有自己的当前位置。注意index
参数也只是这个集合中的位置,所以不需要单独存储。
现在,您需要在调用之间存储一些持久状态,这将是这个 maxDepth
整数字母表位置的数组。你能想出如何编写一个函数来将该数组转换为字符串吗?你能想出如何以与你的递归代码相同的方式将状态推进一位吗?
编辑 你的状态应该类似于
struct PermutationState {
/* stringLength == maxDepth */
int stringLength;
char *string;
/* better to avoid globals */
int alphaLength;
const char *alphabet;
/* this replaces i as the index into our alphabet */
int *alphaPos;
};
我建议写一个像
这样的界面struct PermutationState* start_permutation(int stringLength,
int alphaLength,
const char *alphabet)
{
struct PermutationState *state = malloc(sizeof(*state));
if (!state) return NULL;
/* initialize scalar values first, for easier error-handling */
state->stringLength = stringLength;
state->string = NULL;
state->alphaLength = alphaLength;
state->alphabet = alphabet;
state->alphaPos = NULL;
/* now we can handle nested allocations */
state->string = malloc(stringLength + 1);
state->alphaPos = calloc(stringLength, sizeof(int));
if (state->string && state->alphaPos) {
/* both allocations succeeded, and alphaPos is already zeroed */
memset(state->string, alphabet[0], stringLength);
state->string[stringLength] = 0;
return state;
}
/* one or both of the nested allocations failed */
end_permutation(state);
return NULL;
}
void end_permutation(struct PermutationState *state)
{
free(state->string);
free(state->alphaPos);
free(state);
}
最后你要实现这个功能:
char *next_permutation(struct PermutationState *state)
{
/* TODO */
}
由于 start_permutation
已经为您设置了 state->alphaPos = [0, 0, ... 0]
和 state->string = "aaa...a"
,您可能希望将 alphaPos
提高一个位置,然后 return当前字符串。
注意。我假设您不需要复制字母表,这意味着调用者负责保证其生命周期。如有必要,您也可以轻松复制它。
I just can't figure out how the permutation algorithm works
非常简单:要从一个单词转到下一个单词,从最右边的位置开始,将该字符更改为字母表中的下一个;如果没有下一个字符,则将位置重置为字母表中的第一个字符,然后继续向左更改位置;如果没有剩余位置,则需要加长码字。这是一个示例实现:
char *brute_next()
{
for (; ; )
{
static char *buf; // buffer for codeword
static int maxDepth; // length of codeword
int i, index = maxDepth-1; // alphabet and buffer index, resp.
while (0 <= index) // as long as current length suffices:
{ // next char at buf[index] is next in alphabet or first:
i = buf[index] ? strchr(alphabet, buf[index]) - alphabet + 1 : 0;
if (buf[index] = alphabet[i]) return buf;
buf[index--] = alphabet[0]; // reset to 'a', continue to the left
}
index = maxDepth++; // now need to lengthen the codeword
buf = realloc(buf, maxDepth+1); // string length + terminator
if (!buf) exit(1);
buf[index] = buf[maxDepth] = '[=10=]';
}
}