面试题：“中国浙江杭州”这样的一串字符串有多少个不重复的排序组合？

“中国浙江杭州”这样的一串字符串有多少个不重复的排序组合？要求：长度不变，不能重复。

1) java实现：

import java.util.ArrayList;
import java.util.List;
 
public class StringCombination {
    public static void main(String[] args) {
        String input = "中国浙江杭州";
        int length = 6;
 
        List combinations = generateCombinations(input, length);
        System.out.println("满足条件的组合数量：" + combinations.size());
        System.out.println("满足条件的组合：");
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }
 
    private static List generateCombinations(String input, int length) {
        List combinations = new ArrayList<>();
        generateCombinationsHelper(input, length, "", combinations);
        return combinations;
    }
 
    private static void generateCombinationsHelper(String input, int length, String currentCombination, List combinations) {
        if (currentCombination.length() == length) {
            combinations.add(currentCombination);
            return;
        }
 
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (!currentCombination.contains(String.valueOf(c))) {
                generateCombinationsHelper(input, length, currentCombination + c, combinations);
            }
        }
    }
}

2）C#实现：

csharp
using System;
using System.Collections.Generic;
 
namespace StringCombination
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = "中国浙江杭州";
            int length = 6;
 
            List<string> combinations = GenerateCombinations(input, length);
 
            Console.WriteLine("满足条件的组合数量：" + combinations.Count);
            Console.WriteLine("满足条件的组合：");
            foreach (string combination in combinations)
            {
                Console.WriteLine(combination);
            }
        }
 
        private static List<string> GenerateCombinations(string input, int length)
        {
            List<string> combinations = new List<string>();
            GenerateCombinationsHelper(input, length, "", combinations);
            return combinations;
        }
 
        private static void GenerateCombinationsHelper(string input, int length, string currentCombination, List<string> combinations)
        {
            if (currentCombination.Length == length)
            {
                combinations.Add(currentCombination);
                return;
            }
 
            for (int i = 0; i < input.Length; i++)
            {
                char c = input[i];
                if (!currentCombination.Contains(c.ToString()))
                {
                    GenerateCombinationsHelper(input, length, currentCombination + c, combinations);
                }
            }
        }
    }
}

 3) python实现：

def generate_combinations(input_string, length):
    combinations = []
    generate_combinations_helper(input_string, length, "", combinations)
    return combinations
 def generate_combinations_helper(input_string, length, current_combination, combinations):
    if len(current_combination) == length:
        combinations.append(current_combination)
        return
     for i in range(len(input_string)):
        char = input_string[i]
        if char not in current_combination:
            generate_combinations_helper(input_string, length, current_combination + char, combinations)
 input_string = "上海金燕航空"
length = 6
 combinations = generate_combinations(input_string, length)
print("满足条件的组合数量：", len(combinations))
print("满足条件的组合：")
for combination in combinations:
    print(combination)

4) object-c实现：

objective-c
#import 
 void generateCombinationsHelper(NSString *input, int length, NSString *currentCombination, NSMutableArray *combinations) {
    if (currentCombination.length == length) {
        [combinations addObject:currentCombination];
        return;
    }
     for (int i = 0; i < input.length; i++) {
        unichar c = [input characterAtIndex:i];
        NSString *charString = [NSString stringWithCharacters:&c length:1];
        if (![currentCombination containsString:charString]) {
            generateCombinationsHelper(input, length, [currentCombination stringByAppendingString:charString], combinations);
        }
    }
}
 NSArray *generateCombinations(NSString *input, int length) {
    NSMutableArray *combinations = [NSMutableArray array];
    generateCombinationsHelper(input, length, @"", combinations);
    return combinations;
}
 int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSString *input = @"上海金燕航空";
        int length = 6;
         NSArray *combinations = generateCombinations(input, length);
        NSLog(@"满足条件的组合数量：%lu", (unsigned long)combinations.count);
        NSLog(@"满足条件的组合：");
        for (NSString *combination in combinations) {
            NSLog(@"%@", combination);
        }
    }
    return 0;
}

 5) C++实现：

#include 
#include 
using namespace std;
 void generateCombinationsHelper(string input, int length, string currentCombination, vector& combinations) {
    if (currentCombination.length() == length) {
        combinations.push_back(currentCombination);
        return;
    }
     for (int i = 0; i < input.length(); i++) {
        char c = input[i];
        if (currentCombination.find(c) == string::npos) {
            generateCombinationsHelper(input, length, currentCombination + c, combinations);
        }
    }
}
 vector generateCombinations(string input, int length) {
    vector combinations;
    generateCombinationsHelper(input, length, "", combinations);
    return combinations;
}
 int main() {
    string input = "上海金燕航空";
    int length = 6;
     vector combinations = generateCombinations(input, length);
    cout << "满足条件的组合数量：" << combinations.size() << endl;
    cout << "满足条件的组合：" << endl;
    for (string combination : combinations) {
        cout << combination << endl;
    }
     return 0;
}

 6) c实现：

#include 
#include 
#include 
 void generateCombinationsHelper(char* input, int length, char* currentCombination, char** combinations, int* count) {
    if (strlen(currentCombination) == length) {
        combinations[*count] = malloc((length + 1) * sizeof(char));
        strcpy(combinations[*count], currentCombination);
        (*count)++;
        return;
    }
     for (int i = 0; i < strlen(input); i++) {
        char c = input[i];
        if (strchr(currentCombination, c) == NULL) {
            char* newCombination = malloc((strlen(currentCombination) + 2) * sizeof(char));
            strcpy(newCombination, currentCombination);
            newCombination[strlen(newCombination)] = c;
            newCombination[strlen(newCombination) + 1] = '\0';
            generateCombinationsHelper(input, length, newCombination, combinations, count);
            free(newCombination);
        }
    }
}
 char** generateCombinations(char* input, int length, int* count) {
    char** combinations = malloc(10000 * sizeof(char*));
    *count = 0;
    generateCombinationsHelper(input, length, "", combinations, count);
    return combinations;
}
 int main() {
    char* input = "上海金燕航空";
    int length = 6;
    int count;
     char** combinations = generateCombinations(input, length, &count);
    printf("满足条件的组合数量：%d\n", count);
    printf("满足条件的组合：\n");
    for (int i = 0; i < count; i++) {
        printf("%s\n", combinations[i]);
        free(combinations[i]);
    }
    free(combinations);
     return 0;
}