生成字符串的所有可能排列的列表

Question

我将如何生成包含变量字符列表的长度在x和y字符之间的字符串的所有可能排列的列表.

任何语言都可以使用,但它应该是可移植的.

Answer 1

有几种方法可以做到这一点.常用方法使用递归,memoization或动态编程.基本思想是您生成一个长度为1的所有字符串的列表,然后在每次迭代中,对于在上一次迭代中生成的所有字符串,将该字符串与字符串中的每个字符分别连接起来.(下面代码中的变量索引跟踪最后一次和下一次迭代的开始)

一些伪代码:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

然后你需要删除长度小于x的所有字符串,它们将是列表中的第一个(x-1)*len(originalString)条目.

Answer 2

最好使用回溯

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void print(char *a, int i, int n) {
    int j;
    if(i == n) {
        printf("%s\n", a);
    } else {
        for(j = i; j <= n; j++) {
            swap(a + i, a + j);
            print(a, i + 1, n);
            swap(a + i, a + j);
        }
    }
}

int main(void) {
    char a[100];
    gets(a);
    print(a, 0, strlen(a) - 1);
    return 0;
}

Answer 3

你会得到很多字符串,这是肯定的......

\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(ri)%7D!%7D%20%7D
其中,x和y是你定义它们的方式,r是我们选择的字符数 - - 如果我理解你的话.你肯定应该根据需要生成这些并且不要草率地说,生成一个powerset然后过滤字符串的长度.

以下绝对不是产生这些的最好方法,但它是一个有趣的一面,尽管如此.

Knuth(第4卷,第2节,7.2.1.3)告诉我们(s,t) - 组合相当于重复时一次采取的s + 1项 - 一个(s,t) - 组合是由Knuth等于{t\choose {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.我们可以通过首先以二进制形式生成每个(s,t)组合(因此,长度(s + t))并计算每个1的左边的0的数量来计算出来.

10001000011101 - >成为排列:{0,3,4,4,4,1}

Answer 4

根据Knuth,Python示例的非递归解决方案:

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]<perm[i+1]:
            k0=i
    if k0 == None:
        return None

    l0 = k0+1
    for i in range(k0+1, len(perm)):
        if perm[k0] < perm[i]:
            l0 = i

    perm[k0], perm[l0] = perm[l0], perm[k0]
    perm[k0+1:] = reversed(perm[k0+1:])
    return perm

perm=list("12345")
while perm:
    print perm
    perm = nextPermutation(perm)

Answer 5

您可能会看到" 有效枚举集合的子集 ",它描述了一个算法来完成您想要的部分 - 快速生成长度为x到y的所有N个字符的子集.它包含C中的实现.

对于每个子集,您仍然必须生成所有排列.例如,如果你想要"abcde"中的3个字符,这个算法会给你"abc","abd","abe"......但是你必须将每个字符置换为"acb","bac", "bca"等

Answer 6

一些基于Sarp答案的工作Java代码:

public class permute {

    static void permute(int level, String permuted,
                    boolean used[], String original) {
        int length = original.length();
        if (level == length) {
            System.out.println(permuted);
        } else {
            for (int i = 0; i < length; i++) {
                if (!used[i]) {
                    used[i] = true;
                    permute(level + 1, permuted + original.charAt(i),
                       used, original);
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "hello";
        boolean used[] = {false, false, false, false, false};
        permute(0, "", used, s);
    }
}

Answer 7

这是C#中的一个简单解决方案.

它只生成给定字符串的不同排列.

    static public IEnumerable<string> permute(string word)
    {
        if (word.Length > 1)
        {

            char character = word[0];
            foreach (string subPermute in permute(word.Substring(1)))
            {

                for (int index = 0; index <= subPermute.Length; index++)
                {
                    string pre = subPermute.Substring(0, index);
                    string post = subPermute.Substring(index);

                    if (post.Contains(character))
                            continue;                       

                    yield return pre + character + post;
                }

            }
        }
        else
        {
            yield return word;
        }
    }

Answer 8

这里有很多好的答案.我还建议在C++中使用一个非常简单的递归解决方案.

#include <string>
#include <iostream>

template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
    if (start == s.length()) consume(s);
    for (std::size_t i = start; i < s.length(); i++) {
        std::swap(s[start], s[i]);
        permutations(s, consume, start + 1);
    }
}

int main(void) {
    std::string s = "abcd";
    permutations(s, [](std::string s) {
        std::cout << s << std::endl;
    });
}

注意:具有重复字符的字符串不会产生唯一的排列.

Answer 9

我刚刚在Ruby中快速推出了这个:

def perms(x, y, possible_characters)
  all = [""]
  current_array = all.clone
  1.upto(y) { |iteration|
    next_array = []
    current_array.each { |string|
      possible_characters.each { |c|
        value = string + c
        next_array.insert next_array.length, value
        all.insert all.length, value
      }
    }
    current_array = next_array
  }
  all.delete_if { |string| string.length < x }
end

您可能会查看内置置换类型函数的语言API,并且您可能能够编写更优化的代码,但如果数字都很高,我不确定是否有很多方法可以获得大量结果.

无论如何,代码背后的想法是从长度为0的字符串开始,然后跟踪长度为Z的所有字符串,其中Z是迭代中的当前大小.然后,遍历每个字符串并将每个字符附加到每个字符串上.最后,删除任何低于x阈值的值并返回结果.

我没有使用可能无意义的输入(空字符列表,x和y的奇怪值等)来测试它.

Answer 10

这是Mike的Ruby版本到Common Lisp的翻译:

(defun perms (x y original-string)
  (loop with all = (list "")
        with current-array = (list "")
        for iteration from 1 to y
        do (loop with next-array = nil
                 for string in current-array
                 do (loop for c across original-string
                          for value = (concatenate 'string string (string c))
                          do (push value next-array)
                             (push value all))
                    (setf current-array (reverse next-array)))
        finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))

另一个版本,稍微短一些,使用更多循环设施功能:

(defun perms (x y original-string)
  (loop repeat y
        collect (loop for string in (or (car (last sets)) (list ""))
                      append (loop for c across original-string
                                   collect (concatenate 'string string (string c)))) into sets
        finally (return (loop for set in sets
                              append (loop for el in set when (>= (length el) x) collect el)))))

Answer 11

C++中的递归解决方案

int main (int argc, char * const argv[]) {
        string s = "sarp";
        bool used [4];
        permute(0, "", used, s);
}

void permute(int level, string permuted, bool used [], string &original) {
    int length = original.length();

    if(level == length) { // permutation complete, display
        cout << permuted << endl;
    } else {
        for(int i=0; i<length; i++) { // try to add an unused character
            if(!used[i]) {
                used[i] = true;
                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                used[i] = false;
            }
        }
}

Answer 12

这是一个简单的单词C#递归解决方案:

方法:

public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
        {
            bool finished = true;
            ArrayList newWords = new ArrayList();
            if (words.Count == 0)
            {
                foreach (string letter in letters)
                {
                    words.Add(letter);
                }
            }

            for(int j=index; j<words.Count; j++)
            {
                string word = (string)words[j];
                for(int i =0; i<letters.Length; i++)
                {
                    if(!word.Contains(letters[i]))
                    {
                        finished = false;
                        string newWord = (string)word.Clone();
                        newWord += letters[i];
                        newWords.Add(newWord);
                    }
                }
            }

            foreach (string newWord in newWords)
            {   
                words.Add(newWord);
            }

            if(finished  == false)
            {
                CalculateWordPermutations(letters, words, words.Count - newWords.Count);
            }
            return words;
        }

呼叫:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);

Answer 13

......这是C版本:

void permute(const char *s, char *out, int *used, int len, int lev)
{
    if (len == lev) {
        out[lev] = '\0';
        puts(out);
        return;
    }

    int i;
    for (i = 0; i < len; ++i) {
        if (! used[i])
            continue;

        used[i] = 1;
        out[lev] = s[i];
        permute(s, out, used, len, lev + 1);
        used[i] = 0;
    }
    return;
}

Answer 14

permute(ABC) - > A.perm(BC) - > A.perm [B.perm(C)] - > A.perm [(*B C),(C B*)] - > [(*A BC ),(B A C),(BC A*),(*A CB),(C A B),(CB A*)]在插入每个字母时检查重复项以查看先前的字符串是否以相同的字母结尾(为什么？ - 锻炼)

public static void main(String[] args) {

    for (String str : permStr("ABBB")){
        System.out.println(str);
    }
}

static Vector<String> permStr(String str){

    if (str.length() == 1){
        Vector<String> ret = new Vector<String>();
        ret.add(str);
        return ret;
    }

    char start = str.charAt(0);
    Vector<String> endStrs = permStr(str.substring(1));
    Vector<String> newEndStrs = new Vector<String>();
    for (String endStr : endStrs){
        for (int j = 0; j <= endStr.length(); j++){
            if (endStr.substring(0, j).endsWith(String.valueOf(start)))
                break;
            newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
        }
    }
    return newEndStrs;
}

打印所有排列没有重复

Answer 15

在Perl中,如果要将自己限制为小写字母,可以执行以下操作:

my @result = ("a" .. "zzzz");

这使用小写字符提供1到4个字符之间的所有可能字符串.对于大写字母,改"a"到"A"和"zzzz"到"ZZZZ".

对于混合大小写,它变得更难,并且可能不适合Perl的内置运算符之一.

Answer 16

Ruby的答案有效:

class String
  def each_char_with_index
    0.upto(size - 1) do |index|
      yield(self[index..index], index)
    end
  end
  def remove_char_at(index)
    return self[1..-1] if index == 0
    self[0..(index-1)] + self[(index+1)..-1]
  end
end

def permute(str, prefix = '')
  if str.size == 0
    puts prefix
    return
  end
  str.each_char_with_index do |char, index|
    permute(str.remove_char_at(index), prefix + char)
  end
end

# example
# permute("abc")

Answer 17

import java.util.*;

public class all_subsets {
    public static void main(String[] args) {
        String a = "abcd";
        for(String s: all_perm(a)) {
            System.out.println(s);
        }
    }

    public static Set<String> concat(String c, Set<String> lst) {
        HashSet<String> ret_set = new HashSet<String>();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet<String> all_perm(String a) {
        HashSet<String> set = new HashSet<String>();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i<a.length(); i++) {
                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
            }
        }
        return set;
    }
}

Answer 18

以下Java递归打印给定字符串的所有排列:

//call it as permut("",str);

public void permut(String str1,String str2){
    if(str2.length() != 0){
        char ch = str2.charAt(0);
        for(int i = 0; i <= str1.length();i++)
            permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                     str2.substring(1,str2.length()));
    }else{
    System.out.println(str1);
    }
}

以下是上述"permut"方法的更新版本,它使n!与上述方法相比,(n阶乘)递归调用较少

//call it as permut("",str);

public void permut(String str1,String str2){
   if(str2.length() > 1){
       char ch = str2.charAt(0);
       for(int i = 0; i <= str1.length();i++)
          permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }else{
    char ch = str2.charAt(0);
    for(int i = 0; i <= str1.length();i++)
        System.out.println(str1.substring(0,i) + ch +    str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }
}

Answer 19

我不确定你为什么要首先这样做.任何中等大小的x和y值的结果集将是巨大的,并且随着x和/或y变大而呈指数增长.

假设您的可能字符集是字母表中的26个小写字母,并且您要求您的应用程序生成长度= 5的所有排列.假设您没有内存不足,您将获得11,881,376(即26 5)弦回来.将长度提高到6,你将获得308,915,776个字符串.这些数字非常快,非常快.

这是我用Java编写的解决方案.您需要提供两个运行时参数(对应于x和y).玩得开心.

public class GeneratePermutations {
    public static void main(String[] args) {
        int lower = Integer.parseInt(args[0]);
        int upper = Integer.parseInt(args[1]);

        if (upper < lower || upper == 0 || lower == 0) {
            System.exit(0);
        }

        for (int length = lower; length <= upper; length++) {
            generate(length, "");
        }
    }

    private static void generate(int length, String partial) {
        if (length <= 0) {
            System.out.println(partial);
        } else {
            for (char c = 'a'; c <= 'z'; c++) {
                generate(length - 1, partial + c);
            }
        }
    }
}

Answer 20

这是我在javascript中提出的非递归版本.虽然它在元素交换方面有一些相似之处,但它不是基于Knuth的非递归方法.我已经验证了它对多达8个元素的输入数组的正确性.

快速优化将在out阵列预先飞行并避免push().

基本思路是:

1. 给定单个源数组,生成第一组新数组,这些数组依次交换第一个元素和每个后续元素,每次都不会干扰其他元素.例如:给定1234,生成1234,2134,3214,4231.

2. 使用上一遍中的每个数组作为新传递的种子,但不是交换第一个元素,而是将第二个元素与每个后续元素交换.此外,这次不要在输出中包含原始数组.

3. 重复步骤2直到完成.

这是代码示例:

function oxe_perm(src, depth, index)
{
    var perm = src.slice();     // duplicates src.
    perm = perm.split("");
    perm[depth] = src[index];
    perm[index] = src[depth];
    perm = perm.join("");
    return perm;
}

function oxe_permutations(src)
{
    out = new Array();

    out.push(src);

    for (depth = 0; depth < src.length; depth++) {
        var numInPreviousPass = out.length;
        for (var m = 0; m < numInPreviousPass; ++m) {
            for (var n = depth + 1; n < src.length; ++n) {
                out.push(oxe_perm(out[m], depth, n));
            }
        }
    }

    return out;
}