字符串的排列

//全排列算法+最后map排序即可
#include<iostream>
(720)#include<cstring>
#include<map>
using namespace std;
map<string,int> mm;
void Array(char *s,int k,int m)
{
    if(k==m)
        mm[s]++;
    else
    {
        for(int j=k;j<=m;j++)
        {
            swap(s[j],s[k]);
            Array(s,k+1,m);
            swap(s[j],s[k]);
        }
    }
}
int main()
{
    char s[10];
    cin>>s;
    Array(s,0,strlen(s)-1);
    auto ot=mm.end();
    ot--;
    for(auto it=mm.begin();it!=mm.end();it++)
    {
        if(it==mm.begin())
            cout<<'['<<it->first<<','<<" ";
        else if(it==ot)
            cout<<it->first<<']';
        else
            cout<<it->first<<','<<" ";
    }
}

JavaScript(Node) 😎题目:蘑菇街🍄-字符串全排列无重复（穷举+递归+输出格式(整吐了)）

leetcode46、47

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        let arr = inArr[0].split('')
        let res = permuteUnique(arr).map(e=>e.join(''))
        res.sort()
        let str = ''
        for (let i = 0; i < res.length; i++) {
            if(i==0){
                str += '['+res[i] +', '
            }else if(i==res.length-1){
                str += res[i] +']'
            }else{
                str += res[i]+', '
            }
        }
        console.log(str)
    }
})
var permuteUnique = function(nums) {
    if (nums.length === 0) {
        return [];
    }
    if (nums.length === 1) {
        return [nums];
    }
    
    let [num, ...restNums] = nums;
    let resArr=permuteUnique(restNums).reduce((res, iter) => {
        let iterRes = [];
        for (let i = 0; i <= iter.length; i++) {
            let tmp = [...iter];
            tmp.splice(i, 0, num);
            iterRes.push(tmp);
        }
        return res.concat(iterRes);
    }, []);
    let res={}
        resArr.forEach(item=>{
            res[item]=item;
        });
        return Object.values(res)
};

//dfs+set去重
#include <bits/stdc++.h>
using namespace std;
void dfs(int len,string temp,string &str,vector<bool> &vis,set<string> &ans){
    if(len>=str.size()){
        ans.insert(temp);
        return;
    }
    for(int i=0;i<str.size();i++){
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(len+1,temp+str[i],str,vis,ans);
        vis[i]=false;
    }
}
int main(){
    string str;
    set<string> ans;
    vector<bool> vis(str.size(),false);
    cin>>str;
    dfs(0,"",str,vis,ans);
    set<string>::iterator it=ans.begin();
    cout<<"[";
    while(it!=ans.end()){
        cout<<*it;
        if(++it!=ans.end())
            cout<<", ";
    }
    cout<<"]";
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    //标准的全排列问题，有重复的全排列，偷懒的就用set去重，答案要求字典顺序输出，就用TreeSet咯，
    static TreeSet<String> output = new TreeSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        backtrack(s.toCharArray(), 0, s.length());
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (String item : output) {
            sb.append(item).append(",").append(" ");
        }
        System.out.println(sb.substring(0, sb.length() - 2) + "]");
    }
    //回溯算法
    private static void backtrack(char[] chars, int first, int n) {
        if (first == n) {
            output.add(String.valueOf(chars));
            return;
        }
        for (int i = first; i < n; i++) {
            swap(chars, first, i);
            backtrack(chars, first + 1, n);
            //回溯
            swap(chars, first, i);
        }
    }

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

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    bool isVirgin = true;   //判断是不是第一次
    while(getline(cin,str))
    {
        string result = "";   //结果字符串
        sort(str.begin(), str.end());   //题目中给出的字符串不一定是升序,有个测试点是aA,所以我们自己先升序排列一遍
        do{
            if(isVirgin)
            {
                result += "[" + str;
                isVirgin = false;
            }
            else
            {
                result += ", " + str;  //注意逗号后面有个空格
            }
        }while(next_permutation(str.begin(),str.end()));   //全排列
        result += "]";
        cout << result << endl;
    }
    return 0;
}

import itertools
ss=input()
mm=sorted(set(map(''.join,itertools.permutations(ss))))
print("[" + ', '.join(mm) + "]")
最后输出‘，’后面还有一个空格，要不然格式不正确

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    bool first;
    while(cin>>s){
        first = true;
        string t = "";
        sort(s.begin(), s.end());
        do{
            if(first){
                t = "[" + s;
                first = false;
            }else{
                t += ", " + s;
            }
        }while(next_permutation(s.begin(), s.end()));
        t += "]";
        cout<<t<<endl;
    }
    return 0;
}

package main

import (
    "fmt"
    "sort"
)

func main() {
    var s string
    fmt.Scan(&s)
    
    res := []string{}
    n := len(s)
    st := make([]bool,n)
    visited := make(map[string]bool)

    dfs(s,"",&st,&res,&visited)
    sort.Strings(res)
    for i:=0;i<len(res)-1;i++{
        res[i] = res[i]+","
    }
    fmt.Println(res)
}

func dfs(s string,tmp string,st *[]bool,res *[]string,visited *map[string]bool){
    if (*visited)[tmp]{
        return
    }else{
        (*visited)[tmp] = true
    }
    if len(tmp) == len(s){
        (*res) = append((*res), tmp) 
        return 
    }
    for i:=0 ; i < len(s);i++{
        if !(*st)[i]{
            (*st)[i] = true
            dfs(s,tmp + string(s[i]),st,res,visited)
            (*st)[i] = false
        }
    }
}

package main

import (
	"fmt"
	"sort"
)

func main() {
	var s string
	fmt.Scan(&s)
	res := calStr(s)

	sort.Slice(res, func(i, j int) bool {
		return res[i]+res[j] < res[j]+res[i]
	})

	for i := 0; i < len(res)-1; i++ {
		res[i] += ","
	}
	fmt.Println(res)
}

func calStr(s string) []string {
	res := make([]string, 0)
	m := make(map[string]bool)
	r := []rune(s)
	length := len(r)

	for i := 0; i < length; i++ {
		if length == 2 {
			res = append(res, s)
			r[0], r[1] = r[1], r[0]
			if !m[string(r)] {
				res = append(res, string(r))
				m[string(r)] = true
			}
			break
		} else {
			t := string(r[1:length])
			tmp := calStr(t)
			for _, v := range tmp {
				if !m[string(r[0])+v] {
					res = append(res, string(r[0])+v)
					m[string(r[0])+v] = true
				}
			}
			if i < length-1 {
				r[0], r[i+1] = r[i+1], r[0]
			}
		}
	}
	return res
}

input_str = input()

def back_track(tmp,l, r, res):
    if l == r:
        res.append(''.join(tmp))
        return
    else:
        cache = set()
        for i in range(l, r + 1):
            if tmp[i] in cache:
                pass
            else:
                cache.add(tmp[i])
                tmp[l], tmp[i] = tmp[i], tmp[l]
                back_track(tmp, l + 1, r, res)
                tmp[l], tmp[i] = tmp[i], tmp[l]

result = []
back_track(list(input_str), 0, len(input_str)-1, result)
# 按字典序打印出
result.sort()
print("[" + ', '.join(result) + "]")

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

class Test
{
    static List<string> output = new List<string>();
    static void Main(string[] args)
    {
        string input = Console.ReadLine();

        backtrack(input.ToCharArray(),0 , input.Length);
        
        StringBuilder s = new StringBuilder("[");
        
        delSame();
        
        for(int i = 0;i < output.Count; i++){
            s.Append(output[i]).Append(",").Append(" ");
        }
        s.Remove(s.Length - 2, 2);
        s.Append("]");
        Console.WriteLine(s);
    }
                                            
    private static void backtrack(char[] chars , int first , int n){
        if(first == n){
            output.Add(new string(chars));
            return;
        }
        for(int i = first; i < n; i++){
            swap(chars, first , i);
            backtrack(chars, first + 1, n);
            swap(chars, first , i);
        }
    }
                                            
    private static void swap(char[] chars , int i , int j){
        char temp = chars[j];
        chars[j] = chars[i];
        chars[i] = temp;
    }
    
    private static void delSame(){//去重复
        for (int i = 0; i < output.Count; i++)  //外循环是循环的次数
            {
                for (int j = output.Count - 1 ; j > i; j--)  //内循环是 外循环一次比较的次数
                {

                    if (output[i] == output[j])
                    {
                        output.RemoveAt(j);
                    }

                }
            }
    }
}

#include<bits/stdc++.h>
using namespace std;
vector<string>res;
string t;
void bk(string s,vector<int>&vis)
{
    if(t.size()==s.size())res.push_back(t);
    for(int i=0;i<s.size();i++)
    {
        if(vis[i]==1)continue;
        if(i>0&&s[i]==s[i-1]&&vis[i-1]==0)continue;
        t.push_back(s[i]);
        vis[i]=1;
        bk(s,vis);
        t.pop_back();
        vis[i]=0;
    }
}
int main()
{
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    vector<int>vis(s.size(),0);
    bk(s,vis);
    cout<<'[';
    for(int i=0;i<res.size()-1;i++)
    {
        cout<<res[i]<<','<<" ";
    }
    cout<<res.back()<<']';
    return 0;
}

//深度优先搜索
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <set>

using namespace std;

void DFS_SSP(string s, int k, int m, set<string> &strset) {
    if (k == m) {
        strset.insert(s);
    }
    else {
        for (int i = k; i < m;i++) {
            swap(s[i], s[k]);
            DFS_SSP(s, k+1, m, strset);
            swap(s[i], s[k]);
        }
    }
}

void StringSullPermutation() {
    string s;
    cin>>s;
    int len = s.size();
    set<string> strset; //set自动排序和去重
    DFS_SSP(s, 0, len, strset);
    //输出
    set<string>::iterator it = strset.begin();
    cout << "[";
    while (it != strset.end())
    {
        cout << *it;
        if (++it != strset.end()) {
            cout << ", ";
        }
    }
    cout << "]" <<endl;
}

int main(){
    StringSullPermutation();
    return 0;
}

回溯法  主要在于重复字符的处理
#include<iostream>
(720)#include<string>
#include<vector>
(721)#include<algorithm>

using namespace std;

void BackTrack(string &s, string &temp, vector<string> &ans, vector<bool> &vis){
    if (temp.size() == s.size()){
        ans.push_back(temp);
        return ;
    }
    for (int i = 0; i < s.size(); i++){
        if (vis[i] || (i > 0 && !vis[i-1] && s[i] == s[i-1]))  //控制访问重复或已经访问的字符
            continue;
        vis[i] = true;
        temp.push_back(s[i]);
        BackTrack(s, temp, ans, vis);
        vis[i] = false;
        temp.pop_back();
    }
    return ;
}
int main(void){
    string s;
    cin>>s;
    sort(s.begin(), s.end());
    vector<string> ans;
    string temp;
    vector<bool> vis(s.size(), false);
    BackTrack(s, temp, ans, vis);
    cout<<"[";
    for (int i = 0; i < ans.size(); i++){
        if (i == ans.size()-1)
            cout<<ans[i];
        else
            cout<<ans[i]<<", ";
    }
    cout<<"]"<<endl;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.TreeSet;

public class Permutation {
	//华为机试，字符串处理，排列组合
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String str = input.nextLine();
		List<Character> charList=new ArrayList<Character>();  
        Stack<Character> result=new Stack<Character>();
        TreeSet<String> resultSet = new TreeSet<String>();  //去重加排序
        for(int i = 0;i < str.length();i++){
        	charList.add(str.charAt(i));  
        }
        play(charList,result,resultSet);  
        System.out.println(resultSet);
		input.close();
	}
	
	public static void play(List<Character> charList,Stack<Character> result,TreeSet<String> resultSet){  
      //如果size为1，说明已经排列到最后一个了
      if(charList.size() == 1)  
      {  
    	  result.push(charList.get(0));
    	  resultSet.add(result.toString().replaceAll("[^a-zA-Z]", ""));
          result.pop();  
      }else{  
          for(int i=0;i<charList.size();i++){  
        	  //逐个压栈排列
        	  result.push(charList.get(i));   
              List<Character> tmp=new ArrayList<Character>();  
              for(Character a:charList){
            	  tmp.add(a); 
              }
              //去掉已经压栈的字符
              tmp.remove(i);  
              //排列子序列
              play(tmp,result,resultSet); 
              //移除已排列字符
              result.pop();      
          }  
      }                     
 }  
}