置换字符串直到它匹配一些输入？

Question

我在网上查了一下，没有太多结果，因为很难用几句话来描述。

基本上，我需要一个函数，比如说 puntil，它接受参数 string。基本上，函数置换直到字符串等于参数。

例如，如果你运行 puntil('ab') 它应该在函数内部执行：

一个 b C d 电子 F G H 一世 j k 升米 n o p q r 秒吨你 v w X 是 z 一个 ab！！比赛

另一个例子，对于puntil('abcd')它会做

一个 b C d 电子 F G H 一世 j k 升米 n o p q r 秒吨你 v w X 是 z 一个 ab 交流电广告 ae 自动对焦银啊艾杰啊阿尔是一个奥应用程序水 ar 作为在金影音哇斧头哎呀阿兹

...等等等等.. 直到它匹配 abcd。

基本上是一个无限排列直到它匹配。

有什么想法吗？

Answer 1

OP 的要求有点模棱两可，所以我 post OP 要求的两件事（我怀疑）。

首先，问题可能是，输入字符串在字母表的无限排列中的位置是什么（我认为这是更合理的问题，稍后我会给出原因）。这可以通过以下方式完成：

举个例子（输入=dhca）。因此，所有长度为 1 到 3 个字符的字符串都将出现在该字符串之前。因此，在答案中添加：26^1 + 26^2 + 26^3。然后，第一个字符是d，这意味着，按照字典，如果第一个字符是a | b | c，则所有字符都是有效的。因此，将 3 * 26^3 添加到答案中。现在，假设第一个字符是 d。然后，我们可以得到 a to g (7) 中的所有字符，最后 2 个字符可以是任何字符。因此，将 7 * 26^2 添加到答案中。这样下去，我们得到的答案是：

26^1 + 26^2 + 26^3 + (3 * 26^3) + (7 * 26^2) + (2 * 26^1) + (0) + 1
= 75791

好的。现在是第二件事，我认为 OP 实际上是在问（在我们获得匹配之前打印所有字符串）。现在，为什么我认为这是不可行的，因为如果我们输入 zzzzz（5 个字符长），我们需要打印 26^1 + 26^2 + 26^3 + 26^4 + 26^5 个字符串，即 12356630。因此，对于这部分，我假设输入字符串的最大长度为 5（绝对不会更多），因为对于 6 个字符长度的字符串，我们需要打印 ~321272406 个字符串 --> 不可能。

因此，一个简单的解决方案可以是：

创建一个大小为 27 的数组：arr[] = {'', 'a', 'b', ..., 'y', 'z'}。第一个字符为空。

从 0 到 26（含）写入 5（最大字符串长度）嵌套循环并将其添加到虚拟字符串并打印。有点像。

for i from 0 to 26
    String a = "" + arr[i]
    for j from 0 to 26
        String b = a + arr[j]
        for k from 0 to 26
            String c = b + arr[k]
            for l from 0 to 26
                String d = c + arr[l]
                for m from 0 to 26
                    String e = d + arr[m]
                    print e
                    if(e equals input string)
                        break from all loops //use some flag, goto statement etc.

Answer 2

Fiddle here

function next(charArray, rightBound){

    if(!rightBound){
        rightBound = charArray.length;
    }

    var oldValue = charArray[rightBound-1];
    var newValue = nextCharacter(charArray[rightBound-1]);
    charArray[rightBound-1] = newValue;

    if(newValue < oldValue){
        if(rightBound > 1){
            next(charArray, rightBound-1);
        }
        else{
            charArray.push('a');
        }
    }
    return charArray;
}

function nextCharacter(char){
    if(char === 'z'){
        return 'a'
    }
    else{
        return String.fromCharCode(char.charCodeAt(0) + 1)
    }
}

function permuteUntil(word){
    var charArray = ['a'];
    var wordChain = ['a'];

    while(next(charArray).join('') !== word){
        wordChain.push(charArray.join(''));
    }

    wordChain.push(word);

    return wordChain.join(', ');
}


alert(permuteUntil('ab'));

Answer 3

您要求更优雅的解决方案，这里有一个简单的函数，可将整数转换为小写字符串，使您可以轻松地遍历字符串。

function toWord(val, first, out) {
if(first == 1)
    out = String.fromCharCode(97 + val % 26) + out;
else
    out = String.fromCharCode(97 + (val-1) % 26) + out;
if(val % 26 == 0 && first == 0) {
    val -= 26;
}
else {
    val -= val %26;
}
val = val / 26;
if(val != 0)
    return toWord(val, 0, out);
else
    return out;
}

它绝不是完美的，但它简短而简单。调用函数时设置 val 为要转换的整数，首先为 1，输出为 "".

例如，以下内容会将 yourFunction 应用于前 10,000 个小写字符串

for(int i=0; i<10000; i++) {
    youFunction(toWord(i, 1, ""));
}

Answer 4

所以您需要始终从 a 开始递增？由于它们是 char 值，您可以使用以下结构轻松地做到这一点：

请注意，这是一个 java 解决方案:)

public static char[] increment(char[] arr, int pos) {
    // get current position char
    char currentChar = arr[pos];

    // increment it by one
    currentChar++;

    // if it is at the end of it's range
    boolean overflow = false;
    if (currentChar > 'Z') {
        overflow = true;
        currentChar = 'A';
    }

    // always update current char
    arr[pos] = currentChar;
    if (overflow) {
        if (pos == 0) {
            // resize array and add new character
            char[] newArr = new char[arr.length + 1];
            System.arraycopy(arr, 0, newArr, 0, arr.length);
            newArr[arr.length] = 'A';

            arr = newArr;
        } else {
            // overflowed, increment one position back
            arr = increment(arr, pos - 1);
        }
    }

    return arr;
}


public static void main(String[] args) {
    final String stringToUse = "A";
    final String stringToSearch = "ABCD";

    char[] use = stringToUse.toCharArray();
    for (;;) {
        final String result = new String(use);

        System.out.println("Candidate: " + result);
        if (stringToSearch.equals(result)) {
            System.out.println("Found!");
            break;
        }

        use = increment(use, use.length - 1);
    }
}

Answer 5

这是fiddle

 var alphabet = ['a','b','c'];//,'d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];

 var output = "";
 var match = "cccc";  //<----------- match here

//This is your main function 
function permutate() {

    var d = 0;   // d for depth

    while (true) {

       //Your main alphabet iteration             
       for (var i=0; i<alphabet.length; i++){

          //First level 
          if (d === 0) {
             console.log(alphabet[i])
             output = alphabet[i];
          }    
          else
             iterator(alphabet[i], d);   //Call iterator for d > 0

          if (output === match)
             return;
          }


          d++;  //Increase the depth
       }
 }


 //This function runs n depths of iterations
 function iterator(s, depth){

    if (depth === 0)
       return;

    for (var i=0; i<alphabet.length; i++){

       if (depth > 1)
          iterator(s + alphabet[i], depth - 1)
       else {
          console.log(s + alphabet[i]);
          output = s + alphabet[i];
       } 

       if (output === match)
          return;
    }

 };

解释：

你的程序需要像这样遍历字母表树

[a] 
    -[a]
        -[a] 
             -[a]...
             -[b]...

         [b] ...
    -[b] -
         -[a]...
         -[b]...

[b] - ...
[c] - ...

如果不是因为您需要先完成每个深度的要求，这可以通过传统的递归函数轻松完成。

所以我们需要一个特殊的 iterator(s, depth) 函数，它可以执行请求的嵌套迭代次数（深度）。

所以主函数可以调用深度递增的迭代器(d++)。

就这些了！！

警告：这只是原型。这是可以优化和改进的。它使用全局变量以便于演示。您的真实程序应该避免使用全局变量。如果您的匹配词太长，我还建议在 setTimeout 中调用 iterator()。 n 深度只能受限于你的资源。

置换字符串直到它匹配一些输入？

Permute string until it matches some input?

javascript

algorithm

permutation