找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
基于Mark Byers的回答,我想出了这个解决方案:
JAVA
public class Main {
public static void main(String[] args) {
myPerm("ABCD", 0);
}
private static void myPerm(String str, int index)
{
if (index == str.length()) System.out.println(str);
for (int i = index; i < str.length(); i++)
{
char prefix = str.charAt(i);
String suffix = str.substring(0,i) + str.substring(i+1);
myPerm(prefix + suffix, index + 1);
}
}
}
C#
我还使用新的c# 8.0范围操作符在c#中编写了该函数
class Program
{
static void Main(string[] args)
{
myPerm("ABCD", 0);
}
private static void myPerm(string str, int index)
{
if (index == str.Length) Console.WriteLine(str);
for (int i = index; i < str.Length; i++)
{
char prefix = str[i];
string suffix = str[0..i] + str[(i + 1)..];
myPerm(prefix + suffix, index + 1);
}
}
我们只是把每个字母放在开头,然后排列。 第一次迭代是这样的:
/*
myPerm("ABCD",0)
prefix = "A"
suffix = "BCD"
myPerm("ABCD",1)
prefix = "B"
suffix = "ACD"
myPerm("BACD",2)
prefix = "C"
suffix = "BAD"
myPerm("CBAD",3)
prefix = "D"
suffix = "CBA"
myPerm("DCBA",4)
Console.WriteLine("DCBA")
*/
其他回答
这是一个C解:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char* addLetter(char* string, char *c) {
char* result = malloc(sizeof(string) + 2);
strcpy(result, string);
strncat(result, c, 1);
return result;
}
char* removeLetter(char* string, char *c) {
char* result = malloc(sizeof(string));
int j = 0;
for (int i = 0; i < strlen(string); i++) {
if (string[i] != *c) {
result[j++] = string[i];
}
}
result[j] = '\0';
return result;
}
void makeAnagram(char *anagram, char *letters) {
if (*letters == '\0') {
printf("%s\n", anagram);
return;
}
char *c = letters;
while (*c != '\0') {
makeAnagram(addLetter(anagram, c),
removeLetter(letters, c));
c++;
}
}
int main() {
makeAnagram("", "computer");
return 0;
}
简单的递归c++实现如下所示:
#include <iostream>
void generatePermutations(std::string &sequence, int index){
if(index == sequence.size()){
std::cout << sequence << "\n";
} else{
generatePermutations(sequence, index + 1);
for(int i = index + 1 ; i < sequence.size() ; ++i){
std::swap(sequence[index], sequence[i]);
generatePermutations(sequence, index + 1);
std::swap(sequence[index], sequence[i]);
}
}
}
int main(int argc, char const *argv[])
{
std::string str = "abc";
generatePermutations(str, 0);
return 0;
}
输出:
abc
acb
bac
bca
cba
cab
更新
如果想要存储结果,可以将vector作为函数调用的第三个参数传递。此外,如果您只想要唯一的排列,您可以使用集合。
#include <iostream>
#include <vector>
#include <set>
void generatePermutations(std::string &sequence, int index, std::vector <std::string> &v){
if(index == sequence.size()){
//std::cout << sequence << "\n";
v.push_back(sequence);
} else{
generatePermutations(sequence, index + 1, v);
for(int i = index + 1 ; i < sequence.size() ; ++i){
std::swap(sequence[index], sequence[i]);
generatePermutations(sequence, index + 1, v);
std::swap(sequence[index], sequence[i]);
}
}
}
int main(int argc, char const *argv[])
{
std::string str = "112";
std::vector <std::string> permutations;
generatePermutations(str, 0, permutations);
std::cout << "Number of permutations " << permutations.size() << "\n";
for(const std::string &s : permutations){
std::cout << s << "\n";
}
std::set <std::string> uniquePermutations(permutations.begin(), permutations.end());
std::cout << "Number of unique permutations " << uniquePermutations.size() << "\n";
for(const std::string &s : uniquePermutations){
std::cout << s << "\n";
}
return 0;
}
输出:
Number of permutations 6
112
121
112
121
211
211
Number of unique permutations 3
112
121
211
使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1,因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)
private void getPermutation(String str)
{
if(str==null)
return;
Set<String> StrList = new HashSet<String>();
StringBuilder strB= new StringBuilder();
for(int i = 0;i < (1 << str.length()); ++i)
{
strB.setLength(0); //clear the StringBuilder
for(int j = 0;j < str.length() ;++j){
if((i & (1 << j))>0){ // to check whether jth bit is set
strB.append(str.charAt(j));
}
}
if(!strB.toString().isEmpty())
StrList.add(strB.toString());
}
System.out.println(Arrays.toString(StrList.toArray()));
}
//Rotate and create words beginning with all letter possible and push to stack 1
//Read from stack1 and for each word create words with other letters at the next location by rotation and so on
/* eg : man
1. push1 - man, anm, nma
2. pop1 - nma , push2 - nam,nma
pop1 - anm , push2 - amn,anm
pop1 - man , push2 - mna,man
*/
public class StringPermute {
static String str;
static String word;
static int top1 = -1;
static int top2 = -1;
static String[] stringArray1;
static String[] stringArray2;
static int strlength = 0;
public static void main(String[] args) throws IOException {
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
str = bfr.readLine();
word = str;
strlength = str.length();
int n = 1;
for (int i = 1; i <= strlength; i++) {
n = n * i;
}
stringArray1 = new String[n];
stringArray2 = new String[n];
push(word, 1);
doPermute();
display();
}
public static void push(String word, int x) {
if (x == 1)
stringArray1[++top1] = word;
else
stringArray2[++top2] = word;
}
public static String pop(int x) {
if (x == 1)
return stringArray1[top1--];
else
return stringArray2[top2--];
}
public static void doPermute() {
for (int j = strlength; j >= 2; j--)
popper(j);
}
public static void popper(int length) {
// pop from stack1 , rotate each word n times and push to stack 2
if (top1 > -1) {
while (top1 > -1) {
word = pop(1);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 2);
}
}
}
// pop from stack2 , rotate each word n times w.r.t position and push to
// stack 1
else {
while (top2 > -1) {
word = pop(2);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 1);
}
}
}
}
public static void rotate(int position) {
char[] charstring = new char[100];
for (int j = 0; j < word.length(); j++)
charstring[j] = word.charAt(j);
int startpos = strlength - position;
char temp = charstring[startpos];
for (int i = startpos; i < strlength - 1; i++) {
charstring[i] = charstring[i + 1];
}
charstring[strlength - 1] = temp;
word = new String(charstring).trim();
}
public static void display() {
int top;
if (top1 > -1) {
while (top1 > -1)
System.out.println(stringArray1[top1--]);
} else {
while (top2 > -1)
System.out.println(stringArray2[top2--]);
}
}
}
为排列和组合添加更详细的NcK/NcR
public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}
public static void permNcK(List<String> inputList, int chooseCount, List<String> resultList) {
for (int count = 0; count < inputList.size(); count++) {
permNcK(inputList, "", chooseCount, resultList);
resultList = new ArrayList<String>();
Collections.rotate(inputList, 1);
System.out.println("-------------------------");
}
}
public static void permNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}
public static void main(String[] args) {
List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8" });
List<String> resultList = new ArrayList<String>();
//combinationNcK(positions, "", 3, resultList);
permNcK(positions, 3, resultList);
}
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap