c - 扩展 C 蛮力算法

Question

我需要一个针对字母数字字符的蛮力算法。

我使用的代码只是将所有排列打印到标准输出。我尝试了几个小时，但没能重写代码，以至于我只能调用函数 brute_next() 来在需要时获取下一个代码字。

有人可以帮我重写这段代码吗？函数 brute_next() 应该返回一个 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
}

Answer 1

您正在尝试从递归切换到使用生成器:关键区别在于递归将工作状态隐式存储在调用堆栈中，而生成器需要为下一次调用显式存储其所有状态。

因此，首先您需要考虑在递归版本中隐式为您保留的是什么状态:

• 递归调用的每个级别都有其自己的参数值 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 前进一个位置，然后返回当前字符串。

注意。我假设您不需要复制字母表，这意味着调用者负责保证其生命周期。如有必要，您也可以轻松复制它。