-1

我在这里浏览了所有关于 Permutation String 的方法，我有一个很接近的方法，但它仍然没有达到我的预期。如何从此输入生成输出：输入：5，输出：显示字符串组合 from athrough zzzzz。如果我将 6 作为输入，它将具有 froma的输出zzzzzz。

这里有办法吗？我发现如果我放 3，我应该使用 3 个循环，6 个输入意味着 6 个循环，但我的仍然是静态的，而不是动态的。我的意思是我不能通过 3 个输入进行 3 个循环。

这是我当前的代码： 

String pattern = "abcdefghijklmnopqrstuvxyz";  
String s;  
for (int i = 0; i < pattern.length(); i++) {  
  for (int j = 0; j < pattern.length(); j++) {  
    for (int k = 0; k < pattern.length(); k++) {  
      s = pattern.charAt(i) + "" + pattern.charAt(j) + "" + pattern.charAt(k);  
      System.out.println(s);  
    }  
  }  
}

*编辑：*我上面的代码直接显示5个长度，我希望它从1个长度开始到5个（输入）。

4

4 回答 4

1

这是使用两种相互调用的方法的递归模式示例。

private String pattern = "abcdefghijklmnopqrstuvxyz";
private int numChar = 3;

public void permutateY(String prefix, int charPos, int patternPos) {
    if (patternPos>=pattern.length()) return;

    if (prefix == null) {
        permutateX(String.valueOf(pattern.charAt(patternPos)), charPos+1, 0);
    } else {
        permutateX(prefix + String.valueOf(pattern.charAt(patternPos)), charPos+1, 0);
    }
    permutateY(prefix, charPos, patternPos+1);
}

public void permutateX(String combi, int charPos, int patternPos) {
    if (charPos < numChar) {
        permutateY(combi, charPos, 0);
    } else {
        System.out.println(combi);
    }
}

但是，我完全同意@Stephen C，打印出 26^6 是疯狂的：p

于 2013-07-01T06:12:27.990 回答
1

这将按您的预期工作。但请再次记住斯蒂芬 C 所说的话。

import java.util.*;

public class Main {
public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    Map<Integer, String> myMap = new HashMap<>();
    myMap.put(1, "a");
    myMap.put(2, "b");
    myMap.put(3, "c");
    myMap.put(4, "d");
    myMap.put(5, "e");
    myMap.put(6, "f");
    myMap.put(7, "g");
    myMap.put(8, "h");
    myMap.put(9, "i");
    myMap.put(10, "j");
    myMap.put(11, "k");
    myMap.put(12, "l");
    myMap.put(13, "m");
    myMap.put(14, "n");
    myMap.put(15, "o");
    myMap.put(16, "p");
    myMap.put(17, "q");
    myMap.put(18, "r");
    myMap.put(19, "s");
    myMap.put(20, "t");
    myMap.put(21, "u");
    myMap.put(22, "v");
    myMap.put(23, "w");
    myMap.put(24, "x");
    myMap.put(25, "y");
    myMap.put(26, "z");

    Scanner in = new Scanner(System.in);
    System.out.println("Enter limit here [input type: integer]\n");
    int lim = in.nextInt();
    String[] arr = new String[26 * lim];
    int i = 0;
    int j = lim;
    int k = 1;
    while (i < arr.length) {
        while (lim > 0) {
            arr[i] = myMap.get(k);
            lim--;
            i++;
        }
        lim = j;
        k++;
    }
    print_nCr(arr,arr.length, lim);
}

public static final void print_nCr(String[] arr,final int n, final int r) {
    int[] res = new int[r];
    for (int i = 0; i < res.length; i++) {
        res[i] = i + 1;
    }
    boolean done = false;
    while (!done) {
        for(int i=0;i<res.length;i++){
            System.out.print(arr[res[i]-1]);
        }
        System.out.print("\n");
        done = getNext(res, n, r);
    }
}
public static final boolean getNext(final int[] num, final int n, final int r) {
    int target = r - 1;
    num[target]++;
    if (num[target] > ((n - (r - target)) + 1)) {
        while (num[target] > ((n - (r - target)))) {
            target--;
            if (target < 0) {
                break;
            }
        }
        if (target < 0) {
            return true;
        }
        num[target]++;
        for (int i = target + 1; i < num.length; i++) {
            num[i] = num[i - 1] + 1;
        }
    }
    return false;
}

}

这是您编辑的问题的答案。尝试这个

import java.util.*;

public class Main {
public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    Map<Integer, String> myMap = new HashMap<>();
    myMap.put(1, "a");
    myMap.put(2, "b");
    myMap.put(3, "c");
    myMap.put(4, "d");
    myMap.put(5, "e");
    myMap.put(6, "f");
    myMap.put(7, "g");
    myMap.put(8, "h");
    myMap.put(9, "i");
    myMap.put(10, "j");
    myMap.put(11, "k");
    myMap.put(12, "l");
    myMap.put(13, "m");
    myMap.put(14, "n");
    myMap.put(15, "o");
    myMap.put(16, "p");
    myMap.put(17, "q");
    myMap.put(18, "r");
    myMap.put(19, "s");
    myMap.put(20, "t");
    myMap.put(21, "u");
    myMap.put(22, "v");
    myMap.put(23, "w");
    myMap.put(24, "x");
    myMap.put(25, "y");
    myMap.put(26, "z");

    Scanner in = new Scanner(System.in);
    System.out.println("Enter limit here [input type: integer]\n");
    int lim = in.nextInt();
    String[] arr;
    for(int x=1;x<lim+1;x++){
        arr= new String[26 * x];
        int i = 0;
        int j = x;
        int k = 1;
        while (i < arr.length) {
            while (x > 0) {
                arr[i] = myMap.get(k);
                x--;
                i++;
            }
            x = j;
            k++;
        }
        print_nCr(arr,arr.length, x);

    }

}

public static final void print_nCr(String[] arr,final int n, final int r) {
    int[] res = new int[r];
    for (int i = 0; i < res.length; i++) {
        res[i] = i + 1;
    }
    boolean done = false;
    while (!done) {
        for(int i=0;i<res.length;i++){
            System.out.print(arr[res[i]-1]);
        }
        System.out.print("\n");
        done = getNext(res, n, r);
    }
}
public static final boolean getNext(final int[] num, final int n, final int r) {
    int target = r - 1;
    num[target]++;
    if (num[target] > ((n - (r - target)) + 1)) {
        while (num[target] > ((n - (r - target)))) {
            target--;
            if (target < 0) {
                break;
            }
        }
        if (target < 0) {
            return true;
        }
        num[target]++;
        for (int i = target + 1; i < num.length; i++) {
            num[i] = num[i - 1] + 1;
        }
    }
    return false;
}

}
于 2013-07-01T07:43:49.810 回答
1

我假设这是一个“学习练习”，而不是一个真正的编程问题。（没有人会尝试将26^6（即 3.08 亿）行写入标准输出......）

所以这里有一个提示：

  • 使用递归，以及 StringBuilder 或char[].

我还应该补充一点，这不是排列问题。这是一个组合问题。这里没有排序。而是按顺序生成字符串。

于 2013-07-01T03:42:52.930 回答
1

首先，让我们看看您当前的代码做了什么：

您有整数和i，它们都从 0 开始。整数对应于变量中的字母，您将在字符串的第一个位置使用该字母。整数对应第二个位置，对应第三个位置。jkipatternjk

然后您的循环修改 , 的值i，j并按k以下顺序：

i=0, j=0, k=0 => corresponds to "aaa"
i=0, j=0, k=1 => corresponds to "aab"
i=0, j=0, k=2 => corresponds to "aac"

这种情况一直持续到

i=0, j=0, k=25 => corresponds to "aaz"
i=0, j=1, k=0  => corresponds to "aba"

我们看到j递增 1 并k重置回 0。类似地，当j=25 和k=25 之后，我们将递增1，并将i两者重置为 0。然后我们再次开始递增。它类似于我们的十进制表示法，在 199 之后我们得到 200。jkk

因此，要将其应用于变化的长度，我们需要一种以动态方式存储变量的方法。最好的工具是整数数组。

所以想象一个整数数组int idx[]。它的长度取决于您的输入。您可以像这样初始化它：

int idx[] = new int[n];//where n is the length of the generated strings

现在我们将使用idx来存储整数，如i,j和k，它们将对应于用于生成字符串的字符。例如，如果idx数组的长度为 6 并且具有值 [0,0,2,4,25,25]，它将对应于字符串“aacezz”。

要生成所有可能的字符串，请从idx0 开始所有值（对应于“aaaaaa”），然后创建一个 while 循环。在每次迭代中，您“增加” in 的值idx以获取下一个生成的字符串。这是基本结构的样子

while(/*has more to generate */){
    int i = n - 1;//end of the array
    //decrement i until we see idx[i] != 25 -> Need a loop here!
    //increment idx[i]
    //reset to zero everything to the right of idx[i]. -> Need another loop here!
}

请注意，我没有输入代码 - 只是对 java 注释中应该发生的事情的描述。您应该能够填写其余部分。

祝你好运！

于 2013-07-01T04:24:23.780 回答