用java语言实现递归方法打印给定字符串中所有字符的排列。比如当给定 字符串 String str = ”abc”; 你的程序应能打印出(字符串出现顺序可以和下面给出的顺序不同) abc acb bac bca cab cba

public class StringPermutation {
public static void main(String[] args) {
String str = "abc";
permutation(str.toCharArray(), 0, str.length() - 1);
}

public static void permutation(char[] arr, int start, int end) {
if (start == end) {
System.out.println(arr);
} else {
for (int i = start; i <= end; i++) {
swap(arr, start, i);
permutation(arr, start + 1, end);
swap(arr, start, i);
}
}
}

public static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

相关问题

使用Java语言给定一个字符串，设计一个算法完成对该字符串的一个全排列的输出。比如：字符串 “abc”，输出结果应该是“abc”、“acb”、“bac”、“bca”、“cab” 和 “cba”。 要求：①使用递归思想，编写一个函数 permutationByRecursion，该函数用来生成给定的字符 串的全排列结果。②使用栈数据结构，将①中编写的算法转换成非递归函数，函数名为： permutationByNoRecursion。（利用课堂上讲解的分解 Hanoi 塔的任务方式），该函数所使用的栈 数据结构只能使用自己定义的栈数据结构，不能使用任何语言提供的栈

permutationByRecursion函数的代码如下：

public static void permutationByRecursion(String str, int start, int end) {
    if (start == end) {
        System.out.println(str);
    } else {
        for (int i = start; i <= end; i++) {
            str = swap(str, start, i);
            permutationByRecursion(str, start + 1, end);
            str = swap(str, start, i);
        }
    }
}

public static String swap(String str, int i, int j) {
    char[] charArray = str.toCharArray();
    char temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

permutationByNoRecursion函数的代码如下：

public static void permutationByNoRecursion(String str) {
    Stack<String> stack = new Stack<>();
    stack.push(str);
    while (!stack.isEmpty()) {
        String current = stack.pop();
        if (current.length() == str.length()) {
            System.out.println(current);
        } else {
            for (int i = current.length() - 1; i >= 0; i--) {
                String newStr = swap(current, i, current.length() - 1);
                stack.push(newStr);
            }
        }
    }
}

public static String swap(String str, int i, int j) {
    char[] charArray = str.toCharArray();
    char temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

class Stack<T> {
    private List<T> list = new ArrayList<>();

    public void push(T item) {
        list.add(item);
    }

    public T pop() {
        T item = list.get(list.size() - 1);
        list.remove(list.size() - 1);
        return item;
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

给定一个字符串，设计一个算法完成对该字符串的一个全排列的输出。比如：字符串 “abc”，输出结果应该是“abc”、“acb”、“bac”、“bca”、“cab” 和 “cba”。 要求：①使用递归思想，编写一个函数 permutationByRecursion，该函数用来生成给定的字符 串的全排列结果。②使用栈数据结构，将①中编写的算法转换成非递归函数，函数名为： permutationByNoRecursion。（利用课堂上讲解的分解 Hanoi 塔的任务方式），该函数所使用的栈 数据结构只能使用自己定义的栈数据结构，不能使用任何语言提供的栈

permutationByRecursion函数的代码如下：

#include <iostream>
#include <string>
using namespace std;

void permutationByRecursion(string str, int start, int end) {
    if (start == end) {
        cout << str << endl;
    } else {
        for (int i = start; i <= end; i++) {
            swap(str[start], str[i]);
            permutationByRecursion(str, start + 1, end);
            swap(str[start], str[i]);
        }
    }
}

int main() {
    string str = "abc";
    permutationByRecursion(str, 0, str.size() - 1);
    return 0;
}

permutationByNoRecursion函数的代码如下：

#include <iostream>
#include <string>
using namespace std;

struct Stack {
    char data[100];
    int top;
};

void initStack(Stack &s) {
    s.top = -1;
}

bool isEmpty(Stack &s) {
    return s.top == -1;
}

bool isFull(Stack &s) {
    return s.top == 99;
}

void push(Stack &s, char c) {
    if (isFull(s)) {
        cout << "Stack is full!" << endl;
    } else {
        s.top++;
        s.data[s.top] = c;
    }
}

char pop(Stack &s) {
    if (isEmpty(s)) {
        cout << "Stack is empty!" << endl;
        return '\0';
    } else {
        char c = s.data[s.top];
        s.top--;
        return c;
    }
}

void permutationByNoRecursion(string str) {
    Stack s;
    initStack(s);
    int start = 0;
    int end = str.size() - 1;
    push(s, end);
    while (!isEmpty(s)) {
        end = pop(s);
        if (start == end) {
            cout << str << endl;
            start++;
            if (start <= end) {
                push(s, end);
            }
        } else {
            for (int i = end; i >= start; i--) {
                swap(str[end], str[i]);
                push(s, end - 1);
            }
        }
    }
}

int main() {
    string str = "abc";
    permutationByNoRecursion(str);
    return 0;
}