|
This post is completed by 6 users
|
Add to List |
58. Generate All String Permutations
Objective: Given a String, print all the permutations of it.
Example:
Input : abc Output: abc acb bac bca cba cab
Approach:
- Take one character at a time and fix it at the first position. (use swap to put every character at the first position)
- make recursive call to rest of the characters.
- use swap to revert the string back to its original form fo next iteration.
public class Main {
public static void permutation(char[] arrA, int left, int size) {
int x;
if (left == size) {
for (int i = 0; i < arrA.length; i++) {
System.out.print(arrA[i]);
}
System.out.print(" ");
} else {
for (x = left; x < size; x++) {
swap(arrA, left, x);
permutation(arrA, left + 1, size);
swap(arrA, left, x);
}
}
}
public static void swap(char[] arrA, int i, int j) {
char temp = arrA[i];
arrA[i] = arrA[j];
arrA[j] = temp;
}
public static void main(String[] args) throws java.lang.Exception {
String s = "abc";
char[] arrCh = s.toCharArray();
permutation(arrCh, 0, arrCh.length);
}
}
def permutation(arrA, left, size):
if left == size:
print("".join(arrA), end=" ")
else:
for x in range(left, size):
arrA[left], arrA[x] = arrA[x], arrA[left]
permutation(arrA, left + 1, size)
arrA[left], arrA[x] = arrA[x], arrA[left]
def main():
s = "abc"
arrCh = list(s)
permutation(arrCh, 0, len(arrCh))
if __name__ == "__main__":
main()
package main
import "fmt"
func permutation(arrA []rune, left, size int) {
if left == size {
fmt.Print(string(arrA), " ")
} else {
for x := left; x < size; x++ {
arrA[left], arrA[x] = arrA[x], arrA[left]
permutation(arrA, left+1, size)
arrA[left], arrA[x] = arrA[x], arrA[left]
}
}
}
func main() {
s := "abc"
arrCh := []rune(s)
permutation(arrCh, 0, len(arrCh))
}abc acb bac bca cba cab