字符串排列和递归

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

String permutations and recursion

问题

已经在暑假期间学习了一门编程课程。

这是一个相当标准的作业,我查看了很多帖子和视频,但我就是无法让它工作起来!

作业要求如下:
"完成递归方法,该方法将打印出字符串的所有排列。"

public static void permute(String s, PrintStream out) {
	permute(s, 0, out);
}

private static void permute(String s, int pos, PrintStream out) {
    // 填写你自己的代码
}

我看到了一些解决方案,但由于预定的格式,我有点束手无策。我试着摸索一下,只是为了弄清楚我们用来编译代码的平台。我提出的解决方案不够优美,我真的陷入了困境!

public static void permute(String s, PrintStream out) {
    permute(s, 0, out);
}

private static void permute(String s, int pos, PrintStream out) {
    out.println(s);
    for (int i = pos; i < s.length() - 1; i++) {
        StringBuilder sb = new StringBuilder();
        sb.append(s);
        if (i == pos + 1) {
            sb.setCharAt(0, s.charAt(s.length() - 1));
            sb.setCharAt(2, s.charAt(s.length() - s.length()));
            permute(sb.toString(), i, out);
        } else {
            sb.setCharAt(1, s.charAt(s.length() - 1));
            sb.setCharAt(2, s.charAt(s.length() - 2));
            out.println(sb.toString());
        }
    }
}

它会打印出 ABC ACB CAB CBA。我意识到这段代码存在很多问题。我特意编写它来处理 ABC,然后我打算从那里找解决方法。但结果相当令人失望。

英文:

Been studying a programming course over the summer.

It's a fairly standard assignment and I've looked at alot of posts and videos but i just can't get it to work!

The assignment goes:
"Finish the recursive method that will print all the permutatons of the strings."

public static void permute(String s, PrintStream out) {
	permute(s, 0, out);
}

private static void permute(String s, int pos, PrintStream out) {
    // Fill in your own code
}

I've seen a couple of solutions, but with the pre given format my hands are kinda tied. I played around abit just to get the platform we use to compile tthe code. What I came up with ain't pretty and I'm really stuck!

public static void permute(String s, PrintStream out) {
    permute(s, 0, out);
}

private static void permute(String s, int pos, PrintStream out) {
    out.println(s);
    for (int i = pos; i < s.length() - 1; i++) {
        StringBuilder sb = new StringBuilder();
        sb.append(s);
        if (i == pos + 1) {
            sb.setCharAt(0, s.charAt(s.length() - 1));
            sb.setCharAt(2, s.charAt(s.length() - s.length()));
            permute(sb.toString(), i, out);
        } else {
            sb.setCharAt(1, s.charAt(s.length() - 1));
            sb.setCharAt(2, s.charAt(s.length() - 2));
            out.println(sb.toString());
        }
    }
}

It prints ABC ACB CAB CBA. I do realize there is alot of issues with this code. I wrote it specifically to handle ABC, then I was going to figure it out from there. I came up woefully short.

答案1

得分: 0

你可以使用以下方式来递归地对一个 String 进行排列组合。

static int count = 0;

public static void main(String args[]) {
    permutation("", "JASPER");
    // 给出总排列组合词的数量
    System.out.println(count);
}

private static void permutation(String perm, String word) {
    if (word.isEmpty()) {
        System.err.println(perm + word);
    } else {
        for (int i = 0; i < word.length(); i++) {
            permutation(perm + word.charAt(i), word.substring(0, i)
                    + word.substring(i + 1, word.length()));
            count++;
        }
    }
}

这适用于任何给定的字符串。

英文:

You could use the following way to recursively permutate a String.

static int count = 0;

public static void main(String args[]) {
    permutation(&quot;&quot;, &quot;JASPER&quot;);
    // Gives the total permutated word count
    System.out.println(count);
}

private static void permutation(String perm, String word) {
    if (word.isEmpty()) {
        System.err.println(perm + word);
    } else {
        for (int i = 0; i &lt; word.length(); i++) {
            permutation(perm + word.charAt(i), word.substring(0, i)
                    + word.substring(i + 1, word.length()));
            count++;
        }
    }
}

This works for any given string.

答案2

得分: 0

这是我用来解决问题的代码:

public static void permute(String s, PrintStream out) {
    permute("", s, out);
}

private static void permute(String pre, String rem, PrintStream out) {

    if (rem.length() == 0) {
        out.println(pre);
    }

    for (int i = 0; i < rem.length(); i++) {
        permute(pre+rem.charAt(i), rem.substring(0, i)+rem.substring(i+1, rem.length()), out);
    }
}
感觉加入的参数有点过于繁琐但是我自己找不到其他方法
至少这是递归的方式如果有人有对原始形式的解决方案我将非常乐意接受
英文:

This is what I did to solve it:

public static void permute(String s, PrintStream out) {
	permute(&quot;&quot;, s, out);
}

private static void permute(String pre, String rem, PrintStream out) {

	if (rem.length() == 0) {
		out.println(pre);
	}

	for (int i = 0; i &lt; rem.length(); i++) {
		permute(pre+rem.charAt(i), rem.substring(0, i)+rem.substring(i+1, rem.length()), out);
	}
}

Feels a little bit cheesy with the parameter I added. But I could'nt see another way on my own.
It's recursion atleast, if anyone has a solution to the original form. I'll gladly take it

huangapple
  • 本文由 发表于 2020年8月1日 05:16:52
  • 转载请务必保留本文链接:https://go.coder-hub.com/63199184.html
匿名

发表评论

匿名网友

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

确定