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

我将如何去生成一个长度为x和y的字符串之间的所有可能的排列组合列表,其中包含一个可变的字符列表。

任何语言都可以工作,但它应该是可移植的。

0
额外 编辑
意见: 9
额外 作者 hippietrail,

36 答案

@david: Both @Adam Backtrom and @Viper007Bond give some good advice so I thought I'd take their advice and see if I couldn't implement something, see below.

接下来是一个名为 WP Active Plugins Data 的插件,可在任何时候激活插件时解析所有活动插件的标题元数据,并将每个插件的所有元数据存储到数组中选项在 wp_options 中。我为普通WordPress插件和多站点站点范围的插件设计了它。您可以 从这里下载 ,但我也已将代码复制到此处供您审核:

<?php
/*
Plugin Name: WP Active Plugins Data
Plugin URI: http://mikeschinkel.com/wordpress-plugins/wp-active-plugins-data/
Description: Loads Plugin Data on Plugin Activation and Persists to wp_options for quick retrieval.
Version: 0.1
Author: Mike Schinkel
Author URI: http://mikeschinkel.com
Note: Written for http://wordpress.stackexchange.com/questions/361/is-there-a-way-for-a-plug-in-to-get-its-own-version-number
*/

require_once(ABSPATH.'wp-admin/includes/plugin.php');

function get_active_plugin_version($plugin_path_file, $sitewide = false) {
    return get_active_plugin_attribute($plugin_path_file,'Version');
}
function get_active_plugin_attribute($plugin_path_file, $attribute) {
    $all_plugins_data = get_active_plugins_data($plugin_path_file,$sitewide);
    return (isset($all_plugins_data[$attribute]) ? $all_plugins_data[$attribute] : false);
}
function get_active_plugins_data($plugin_path_file, $sitewide = false) {
    $failsafe = false;
    $plugin = plugin_basename(trim($plugin_path_file));
    $sitewide = (is_multisite() && ( $sitewide || is_network_only_plugin($plugin)));
    if ($sitewide) {
        $all_plugins_data = get_site_option('active_sitewide_plugin_data',array());
    } else {
        $all_plugins_data = get_option('active_plugin_data',array());
    }
    if (!$failsafe && !is_array($all_plugins_data) || count($all_plugins_data)==0) {
        $failsafe = true;//Don't risk infinite recursion
        if ($sitewide) {
            $active_plugins = get_site_option('active_sitewide_plugins',array());
        } else {
            $active_plugins = get_option('active_plugins',array());
        }
        persist_active_plugin_data(null,$active_plugins,$sitewide);
        $all_plugins_data = get_active_plugin_version($plugin_path_file,$sitewide);
    }
    return $all_plugins_data[$plugin_path_file];
}
add_action('update_site_option_active_sitewide_plugins','persist_sitewide_active_plugin_data',10,2);
function persist_sitewide_active_plugin_data($option, $plugins) {
    persist_active_plugin_data(null,$plugins,'sitewide');
}
add_filter('update_option_active_plugins','persist_active_plugin_data',10,2);
function persist_active_plugin_data($old_plugins, $new_plugins, $sitewide=false) {
    $active_plugin_data = array_flip($new_plugins);
    $plugin_dir = WP_PLUGIN_DIR;
    foreach($new_plugins as $plugin) {
        $active_plugin_data[$plugin] = get_plugin_data("$plugin_dir/$plugin");
    }
    if ($sitewide)
        update_site_option('active_sitewide_plugin_data',$active_plugin_data);
    else
        update_site_option('active_plugin_data',$active_plugin_data);
}

想看看它是如何工作的?这里有一个测试文件,你可以放在你的WordPress站点的根目录下( http://example.com/test.php 。)确保你在测试之前已经激活了这个插件和Akismet。

<?php
/*
* test.php - Place in root of WordPress website.
*
* Before running be sure to activate both Akismet and the WP Active Plugin Data plugin
*
*/

include "wp-load.php";

header('Content-type:text/plain');
$akismet = "akismet/akismet.php";
echo "Akismet Version: " . get_active_plugin_version($akismet);
echo "\n\nAkismet Description: " . get_active_plugin_attribute($akismet,'Description');
echo "\n\nAll Akismet Data:\n";
print_r(get_active_plugins_data($akismet));

如果这不是你所需要的,至少它应该给你一个很好的起点。希望这可以帮助。

9
额外
+1。干得不错,迈克。我不知道有多少插件会从这个StackExchange中出来。 :)
额外 作者 Annika Backstrom,
谢谢。其实,我希望很多,但我也希望只有最好的方式进入存储库。现在有太多的垃圾了!
额外 作者 MikeSchinkel,

你可以解析你的插件的元数据(文件顶部的东西),但是如果你只用一个匹配的版本号来设置你自己的PHP变量,性能会更好。当你更新插件时,只需更新两个版本号。

在短期内,你的工作稍微多些,但从长远来看要好得多。

2
额外
只需定义一个变量,性能可能会更好,但在两个位置更改版本号也不太好。对于主题,有一个类似的函数wp_get_theme甚至用于例子中: codex.wordpress.org/Child_Themes在WordPress中看起来像一个糟糕的设计,如果我们可以通过变量设置插件版本,然后通过wp_enqueue_style和wp_enqueue_script函数重新使用变量,那将会更好。
额外 作者 baptx,

在管理屏幕中有: get_plugin_data()。在模板中,我认为您需要插件来将这些数据保存在PHP中,例如设置一个常量或全局或其他内容,并将该值与插件头版本号保持同步。

wp-settings.php calls wp_get_active_and_valid_plugins(), which pulls data from the active_plugins site option. This option only contains the path to the plugin file, and wp-settings.php only runs include_once on the file, so it's never parsed for the plugin metadata.

1
额外

我刚刚在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值等)。

0
额外
此代码是错误的。它会产生无效的排列,如重复字符的排列。例如,对于字符串“abc”,它会生成大小为3的这些排列:[“aaa”,“aab”,“aac”,“aba”,“abb”,“abc”,“aca”,“acb” acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac “,”cba“,”cbb“,”cbc“,”cca“,”ccb“,”ccc“]。这是不正确的。
额外 作者 pmc255,

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

\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey%20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
Where, x and y is how you define them and r is the number of characters we are selecting from --if I am understanding you correctly. You should definitely generate these as needed and not get sloppy and say, generate a powerset and then filter the length of strings.

以下绝对不是产生这些的最佳方式,但这是一个有趣的撇弃,无所不在。

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 --> becomes the permutation: {0, 3, 4, 4, 4, 1}

0
额外

虽然这并不能完全回答你的问题,但是这里有一种方法可以从一些长度相同的字符串中产生字母的每个排列:例如,如果你的单词是“咖啡”,“joomla”和“moodle”,你可以期望输出如“coodle”,“joodee”,“joffle”等。

基本上,组合的数量是(字数)与(每字的字母数)的幂。因此,选择0到组合数之间的一个随机数 - 1,将该数字转换为基数(字数),然后使用该数字的每个数字作为从哪个字开始取下一个字母的指示符。

例如:在上面的例子中。 3个字,6个字母= 729个组合。选择一个随机数字:465.转换为基数3:122020.从第一个字母开始,从第二个字节开始第二个字节,从第二个字节开始第三个字节,从第0个字节开始第四个字符......并得到......“joofle”。

如果你想要所有的排列组合,只需从0到728循环。当然,如果你只是选择一个随机值,那么更简单的方法就是循环遍历字母。这种方法可以避免递归,如果你想要所有的排列,再加上它让你看起来像你知道的数学(tm)

如果组合数量过多,可以将它分解为一系列较小的单词并在最后连接它们。

0
额外

Here is a link that describes how to print permutations of a string. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

0
额外
0
额外
作为评论,请注意,对于重复字符的字符串,这不会产生独特的排列。这可以用散列来解决,但这可能是长字符串的问题。
额外 作者 Glenn,
你可能想要使用char数组而不是字符串来使它运行得更快,因为字符串在java中是不可变的。
额外 作者 Abhijeet Kashnia,
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list 

def func( x,i,j ): #returns x[i..j]
z = '' 
for i in range(i,j+1):
    z = z+x[i]
return z 

def perm( x , length , list ): #perm function
if length == 1 : # base case
    list.append( x[len(x)-1] )
    return list 
else:
    lists = perm( x , length-1 ,list )
    lists_temp = lists #temporarily storing the list 
    lists = []
    for i in range( len(lists_temp) ) :
        list_temp = gen(lists_temp[i],x[length-2],lists)
        lists += list_temp 
    return lists
0
额外

在Perl中,如果你想限制自己的小写字母,你可以这样做:

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

这使用小写字符给出1到4个字符之间的所有可能的字符串。对于大写字母,请将“a”更改为“A”“zzzz”“ZZZZ”

对于混合用例来说,它变得更加困难,并且可能不适合Perl这样的内置运算符。

0
额外

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")
0
额外
对于Ruby中的花哨的一行: stackoverflow.com/questions/5773961/…
额外 作者 dojosto,

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

一个快速优化可以预先调用 out 数组并避免 push()

基本的想法是:

    给定一个源数组,生成第一个新的数组集合,它将第一个元素与每个后续元素依次交换,每次将其他元素置于不受干扰的位置。 例如:给定1234,产生1234,2134,3214,4231。
  1. 使用前一遍中的每个数组作为新传球的种子, 但不是交换第一个元素,请将第二个元素与每个后续元素交换。此外,这次不要在输出中包含原始数组。

  2. 重复第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;
}
0
额外

中有一个迭代Java实现(适用于对象列表):

/**
 * Generate the indices into the elements array for the next permutation. The
 * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its 
 * Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
 */
private void generateNextPermutationIndices()
{
    if (remainingPermutations == 0)
    {
        throw new IllegalStateException("There are no permutations " +
             "remaining. Generator must be reset to continue using.");
    }
    else if (remainingPermutations < totalPermutations)
    {
        // Find largest index j with 
        // permutationIndices[j] < permutationIndices[j + 1]
        int j = permutationIndices.length - 2;
        while (permutationIndices[j] > permutationIndices[j + 1])
        {
            j--;
        }

        // Find index k such that permutationIndices[k] is smallest integer 
        // greater than permutationIndices[j] to the right
        // of permutationIndices[j].
        int k = permutationIndices.length - 1;
        while (permutationIndices[j] > permutationIndices[k])
        {
            k--;
        }

        // Interchange permutation indices.
        int temp = permutationIndices[k];
        permutationIndices[k] = permutationIndices[j];
        permutationIndices[j] = temp;

        // Put tail end of permutation after jth position in increasing order.
        int r = permutationIndices.length - 1;
        int s = j + 1;

        while (r > s)
        {
            temp = permutationIndices[s];
            permutationIndices[s] = permutationIndices[r];
            permutationIndices[r] = temp;
            r--;
            s++;
        }
    }
    --remainingPermutations;
}

/**
 * Generate the next permutation and return a list containing
 * the elements in the appropriate order.  This overloaded method
 * allows the caller to provide a list that will be used and returned.
 * The purpose of this is to improve performance when iterating over
 * permutations.  If the {@link #nextPermutationAsList()} method is
 * used it will create a new list every time.  When iterating over
 * permutations this will result in lots of short-lived objects that
 * have to be garbage collected.  This method allows a single list
 * instance to be reused in such circumstances.
 * @param destination Provides a list to use to create the
 * permutation.  This is the list that will be returned, once
 * it has been filled with the elements in the appropriate order.
 * @return The next permutation as a list.
 */
public List nextPermutationAsList(List destination)
{
    generateNextPermutationIndices();
    // Generate actual permutation.
    destination.clear();
    for (int i : permutationIndices)
    {
        destination.add(elements[i]);
    }
    return destination;
}

完整来源

0
额外

您可以查看“有效枚举集合的子集”,其中描述了执行部分的算法你想要的 - 快速生成从长度x到y的N个字符的所有子集。它包含一个在C中的实现。

对于每个子集,您仍然必须生成所有排列。例如,如果你想要“abcde”中的3个字符,这个算法会给你“abc”,“abd”,“abe”...... 但你必须对每一个进行排列才能得到“acb”,“bac”,“bca”等。

0
额外

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

#include 
#include 

template
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;
    });
}

Note: strings with repeated characters will not produce unique permutations.

0
额外
这个解决方案非常好,值得更多关注。
额外 作者 Mike S,
def permutation(str)
  posibilities = []
  str.split('').each do |char|
    if posibilities.size == 0
      posibilities[0] = char.downcase
      posibilities[1] = char.upcase
    else
      posibilities_count = posibilities.length
      posibilities = posibilities + posibilities
      posibilities_count.times do |i|
        posibilities[i] += char.downcase
        posibilities[i+posibilities_count] += char.upcase
      end
    end
  end
  posibilities
end

这是我的一个非递归版本

0
额外

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

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]< 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)
0
额外
有趣的是 nextPermutation()是无状态的?它只需要输入进行置换,并且索引不会从迭代到迭代。通过假设初始输入已排序并根据排序的维护位置找到索引( k0l0 )本身,可以这样做。对像“54321” - >“12345”这样的输入进行排序可以使该算法找到所有预期的排列。但是,由于它为生成的每个排列重新查找这些索引做了大量的额外工作,因此可以非递归地进行更有效的方法。
额外 作者 spaaarky21,
实际上,当字符串未被排序时,这不会不工作。如果您使用“54321”进行尝试,则只会显示一个字符串(本身)。
额外 作者 tonjo,

pythonic解决方案:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
0
额外

...这里是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;
}
0
额外

有几种方法可以做到这一点。常用方法使用递归,记忆或动态编程。基本思想是,你产生一个长度为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)条目。

0
额外
为什么首先存储元素列表,然后清除它? (参考伪代码中的第1行和第3行)。
额外 作者 Håvard Geithus,
y(第4行)是什么?
额外 作者 Jaseem,
@Jaseem从这个问题:“长度为x和长度的字符串之间的所有可能的排列组合”
额外 作者 cksubs,

我不确定你为什么想要这样做。任何中等大小的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);
            }
        }
    }
}
0
额外
很长一段时间,但你不是重复生成它们吗?
额外 作者 Kakira,

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
0
额外
@Sarp Centel:这个代码在C ++中工作吗? <<�代码>串</代码>>
额外 作者 Lazer,

这里是一个简单的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

调用:</强>

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

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

它只产生给定字符串的不同排列。

    static public IEnumerable 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;
        }
    }
0
额外
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 concat(String c, Set lst) {
        HashSet ret_set = new HashSet();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet all_perm(String a) {
        HashSet set = new HashSet();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i
0
额外
额外 作者 MLProgrammer-CiM,

permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] To remove duplicates when inserting each alphabet check to see if previous string ends with the same alphabet (why? -exercise)

public static void main(String[] args) {

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

static Vector permStr(String str){

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

    char start = str.charAt(0);
    Vector endStrs = permStr(str.substring(1));
    Vector newEndStrs = new Vector();
    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;
}

打印所有排列无重复

0
额外

python中的这段代码在被 allowed_characters 设置为 [0,1] 且最多4个字符时调用时会生成2 ^ 4个结果:

<0000>'0001''0010''0011''0100''0101''0110'0111'1000''1001''1010''1011 ','1100','1101','1110','1111']

def generate_permutations(chars = 4) :

#modify if in need!
    allowed_chars = [
        '0',
        '1',
    ]

    status = []
    for tmp in range(chars) :
        status.append(0)

    last_char = len(allowed_chars)

    rows = []
    for x in xrange(last_char ** chars) :
        rows.append("")
        for y in range(chars - 1 , -1, -1) :
            key = status[y]
            rows[x] = allowed_chars[key] + rows[x]

        for pos in range(chars - 1, -1, -1) :
            if(status[pos] == last_char - 1) :
                status[pos] = 0
            else :
                status[pos] += 1
                break;

    return rows

import sys


print generate_permutations()

希望这对你有用。适用于任何角色,不仅是数字

0
额外
这不是排列,而是子集选择,即ABC&001 = C,而有效排列必须包含所有三个字符。
额外 作者 Schultz9999,
呃?对不起,我不明白你说什么。如果你修复它留下一个固定的版本,我会社区wiki的事情
额外 作者 droope,

我今天需要这个,尽管已经给出的答案指出了我正确的方向,但它们并不是我想要的。

这是一个使用Heap方法的实现。阵列的长度必须至少为3,实际考虑因素不能大于10,这取决于你想要做什么,耐心和时钟速度。

在你进入你的循环之前,首先用第一个变量 Stack(3 To N)初始化 Perm(1 To N),然后用零*和 Level with 2 **。在循环结束时调用 NextPerm ,当我们完成后它将返回false。

* VB会为你做到这一点。

**您可以稍微更改NextPerm以使其不必要,但它更清晰。

Option Explicit

Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
    Swap Perm(1), Perm(2)
    Level = 3
Else
    While Stack(Level) = Level - 1
        Stack(Level) = 0
        If Level = UBound(Stack) Then Exit Function
        Level = Level + 1
    Wend
    Stack(Level) = Stack(Level) + 1
    If Level And 1 Then N = 1 Else N = Stack(Level)
    Swap Perm(N), Perm(Level)
    Level = 2
End If
NextPerm = True
End Function

Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub

'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
    A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
    If CurrentY + TextHeight("0") > ScaleHeight Then
        ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
        CurrentY = 0
        CurrentX = 0
    End If
    T = vbNullString
    For I = 1 To UBound(A)
        Print A(I);
        T = T & Hex(A(I))
    Next
    Print
    Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
    J = J * I
Next
If J <> Test.Count Then Stop
End Sub

其他方法由各种作者描述。 Knuth描述了两种,一种给出了词汇顺序,但是复杂而缓慢,另一种被称为明显变化的方法。高洁和王殿军也写了一篇有趣的论文。

0
额外

最好使用回溯

#include 
#include 

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;
}
0
额外
最佳解决方案everrrrrrrrr
额外 作者 GrowinMan,
这是一个很容易阅读和易于掌握的外观。
额外 作者 joey rohan,

c#迭代:

public List Permutations(char[] chars)
    {
        List words = new List();
        words.Add(chars[0].ToString());
        for (int i = 1; i < chars.Length; ++i)
        {
            int currLen = words.Count;
            for (int j = 0; j < currLen; ++j)
            {
                var w = words[j];
                for (int k = 0; k <= w.Length; ++k)
                {
                    var nstr = w.Insert(k, chars[i].ToString());
                    if (k == 0)
                        words[j] = nstr;
                    else
                        words.Add(nstr);
                }
            }
        }
        return words;
    }
0
额外

以下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()));
   }
}
0
额外
@TaoZhang感谢补充,我没有从任何地方复制它,但有可能有人创建了类似的算法。无论如何,我已更新上面的代码少递归调用
额外 作者 Ramy,
这是最干净的解决方案,我相信我之前在“破解编码访谈”一书中看到过它。
额外 作者 Tao Zhang,

Python中的递归解决方案。关于这段代码的好处是,它会导出一个字典,其中键为字符串,所有可能的排列都作为值。所有可能的字符串长度都包含在内,所以实际上,您正在创建超集。

如果您只需要最终的排列,则可以从字典中删除其他键。

在这段代码中,排列的字典是全局的。

在基本情况下,我将该值作为两种可能性存储在列表中。 perms ['ab'] = ['ab','ba']

对于较高的字符串长度,该函数指的是较低的字符串长度,并包含以前计算的排列。

该功能有两件事:

  • 用较小的字符串
  • 调用它自己 如果已经可用,
  • 返回特定字符串的排列列表。如果返回自己,这些将用于附加到角色并创建更新的排列。

内存昂贵。

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]
0
额外

带有驱动程序 main()方法的递归解决方案。

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if(remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i

}

0
额外

那么这里是一个优雅的,非递归的O(n!)解决方案:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }
0
额外

为Java语言编写的代码:

包namo.algorithms;

import java.util.Scanner;

公共课Permuations {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if(currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

0
额外

可能的字符串排列可以使用递归函数来计算。以下是可能的解决方案之一。

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList getPerm(String s, int index) {
        ArrayList perm = new ArrayList();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
0
额外