如何找到一个字符串中所有不重复字符的排列?

huangapple go评论149阅读模式
英文:

How to find permutations of a string with all distinct characters?

问题

The role of the "rem" variable in the code is to represent the remaining characters of the input string "str" after removing the character at the current position (index "i"). It is used to recursively generate permutations of the string by repeatedly removing one character at a time and adding it to the "prefix" string.

英文:

I have found a piece of code in a book which claims to print all permutations of a string with all distinct characters :-

void permutation(String str) {
    permutation(str, "");
}
    
void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

What is the role of the rem variable in the code?

答案1

得分: 2

你可以可视化这个过程。

static int indent = 0;
static String indent(int i) { return "  ".repeat(i); }

void permutation(String str) {
    System.out.println("permutation(\"" + str + "\")");
    ++indent;
    permutation(str, "");
}

void permutation(String str, String prefix) {
    System.out.println(indent(indent) + "permutation(\"" + str + "\", \"" + prefix + "\")");
    if (str.length() == 0) {
        System.out.println(indent(indent + 1) + "--> " + prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            ++indent;
            permutation(rem, prefix + str.charAt(i));
            --indent;
        }
    }
}

permutation("abc");

输出

permutation("abc")
  permutation("abc", "")
    permutation("bc", "a")
      permutation("c", "ab")
        permutation("", "abc")
          --> abc
        permutation("b", "ac")
          permutation("", "acb")
          --> acb
      permutation("ac", "b")
        permutation("c", "ba")
          permutation("", "bac")
          --> bac
        permutation("a", "bc")
          permutation("", "bca")
          --> bca
    permutation("ab", "c")
      permutation("b", "ca")
        permutation("", "cab")
          --> cab
        permutation("a", "cb")
          permutation("", "cba")
          --> cba
英文:

You can visualize the process.

static int indent = 0;
static String indent(int i) { return &quot;  &quot;.repeat(i); }

void permutation(String str) {
    System.out.println(&quot;permutation(\&quot;&quot; + str + &quot;\&quot;)&quot;);
    ++indent;
    permutation(str, &quot;&quot;);
}


void permutation(String str, String prefix) {
    System.out.println(indent(indent) + &quot;permutation(\&quot;&quot; + str + &quot;\&quot;, \&quot;&quot; + prefix + &quot;\&quot;)&quot;);
    if (str.length() == 0) {
        System.out.println(indent(indent + 1) + &quot;--&gt; &quot;+ prefix);
    } else {
        for (int i = 0; i &lt; str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            ++indent;
            permutation(rem, prefix + str.charAt(i));
            --indent;
        }
    }
}

and

permutation(&quot;abc&quot;);

output

permutation(&quot;abc&quot;)
  permutation(&quot;abc&quot;, &quot;&quot;)
    permutation(&quot;bc&quot;, &quot;a&quot;)
      permutation(&quot;c&quot;, &quot;ab&quot;)
        permutation(&quot;&quot;, &quot;abc&quot;)
          --&gt; abc
      permutation(&quot;b&quot;, &quot;ac&quot;)
        permutation(&quot;&quot;, &quot;acb&quot;)
          --&gt; acb
    permutation(&quot;ac&quot;, &quot;b&quot;)
      permutation(&quot;c&quot;, &quot;ba&quot;)
        permutation(&quot;&quot;, &quot;bac&quot;)
          --&gt; bac
      permutation(&quot;a&quot;, &quot;bc&quot;)
        permutation(&quot;&quot;, &quot;bca&quot;)
          --&gt; bca
    permutation(&quot;ab&quot;, &quot;c&quot;)
      permutation(&quot;b&quot;, &quot;ca&quot;)
        permutation(&quot;&quot;, &quot;cab&quot;)
          --&gt; cab
      permutation(&quot;a&quot;, &quot;cb&quot;)
        permutation(&quot;&quot;, &quot;cba&quot;)
          --&gt; cba

huangapple
  • 本文由 发表于 2020年8月11日 20:58:07
  • 转载请务必保留本文链接:https://go.coder-hub.com/63358647.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定