问题标签 [permutation]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
9 回答
18824 浏览

java - 查找给定数字集的所有组合

假设我有一组数字“0”、“1”、“2”、...、“9”。我想找到所有恰好包含我的集合中每个数字之一的数字。

问题是:在我开始我的程序之前,我不知道我的集合将包含多少个数字和哪些数字。(例如,该集合可以包括数字“1”、“3”和“14”。)

我搜索了互联网,偶然发现了“动态编程”这个词,它显然是用来解决像我这样的问题的,但我不明白这些例子。

有人可以给我一个关于如何解决这个问题的提示(可能使用动态编程)吗?

编辑:当集合包括像“14”这样的数字时,集合的不同数字当然必须通过某种方式分开,例如当集合包括数字“1”、“3”和“14”时,组合可以类似于 1-3-14 或 3-14-1 (= 由“-”字符分隔的单个数字)。

编辑2:这里描述了一个似乎有点相似的问题:其中一种解决方案使用动态编程。

0 投票
20 回答
35374 浏览

c++ - 有没有更好的方法来排列字符串?

上面的函数显示了str(withstr[0..mid-1]作为一个稳定的前缀和str[mid..end]作为一个可置换的后缀) 的排列。所以我们可以用它permute(str, 0, str.size() - 1)来显示一个字符串的所有排列。

但是该函数使用递归算法;也许它的性能可以提高?

有没有更好的方法来置换字符串?

0 投票
4 回答
10770 浏览

iterator - 一次一个交换遍历所有排列

给定一个包含 n 个不同项目的列表,我如何逐步遍历项目的每个排列,一次只交换一对值?(我认为这是可能的,当然感觉应该是这样。)

我正在寻找的是一个迭代器,它产生下一对要交换的项目的索引,这样如果迭代 n!-1 次,它将逐步通过 n! 以某种顺序排列列表。如果再次迭代它会将列表恢复到其起始顺序,那将是一个奖励,但这不是必需的。如果所有对都将第一个(分别是最后一个)元素作为一对中的一个,那么函数只需要返回一个值,那也将是一个奖励。

示例:- 对于 3 个元素,您可以将最后一个元素与第一个和第二个元素交替交换以循环排列,即: (abc) swap 0-2 => (cba) 1-2 (cab) 0-2 ( bac) 1-2 (bca) 0-2 (acb)。

我将在 C 中实现,但可能会在大多数语言中找出解决方案。

0 投票
6 回答
694 浏览

c - 创建固定大小数组的每个可能值

我正在尝试制作一些非常基本的东西,它将循环遍历数组的所有可能排列。

确实这是在汇编中完成的,但我将在 C 中解释它。

基本上,假设我们有一个数组uint8_t *data=malloc(10);

我想创建一个算法来打印数组中所有可能的字节组合data

是的,我知道它会很慢(并且有很多值),而且我并不是要真正复杂的优化版本。我只是在寻找可以在我的计算机上运行的东西,作为一种蛮力-force 类型的东西来找到符合某些条件的某些值..

(注意,我说排列是​​因为 [0,1,2] 不应该被视为与 [2,1,0] 相同)

编辑:另外,尽量不要使用太多的 libc 函数,因为我会将它转换为只有 512 字节的独立引导加载程序。

我知道我知道如何做到这一点,但是对于我的一生,我就是无法让算法在我的脑海中运行!

0 投票
1 回答
2948 浏览

c# - 是否有可以进行字符串排列或字符串扩展的 .NET 库?

我正在寻找的是一些库或一些类代码,可用于将构造字符串扩展为变体和排列。类似于以下内容(语法是我的,可能不同):

虽然自己构建它不会太难,但如果它存在,为什么还要重新发明轮子呢?

0 投票
4 回答
517 浏览

algorithm - 假设一个数字大于另一个数字,则 2 个数字的可能结果数

我正在尝试编写一个算法来计算结果。但我需要组合数学方面的帮助。

假设我必须从 1 到 10 中选择 2 个数字。根据计数的基本规则,在没有任何限制的情况下,可能结果的数量是 10 * 10 = 100。(选择第一个数字的 10 个可能结果 x 10 个可能选择第二个的结果)。

鉴于第一个数字必须大于第二个数字,可能的结果数量是多少?

0 投票
2 回答
1993 浏览

java - 一串单词的排列(排序),但中间用逗号分隔

我在让这段代码在用逗号分隔的字符串上生成许多排列(排序)时遇到了一些困难......我可以只做一个普通的字符串,让排列只对字母起作用,但做起来有点困难它用逗号分隔的单词...

为了让程序识别逗号,我使用了 StringTokenizer 方法,并将其放入 arrayList 中,但这实际上是我所得到的......问题再次是我在排列每个单词时遇到了麻烦......举个例子,我将在下面发布它,然后在下面发布我的代码……谢谢大家的帮助!...通过排列,我的意思是用逗号分隔的单词的顺序

例如,如果 BufferedReader 上的输入看起来像:

PrintWriter 上的输出应如下所示:

请注意,输入总共有 3 行,包括“一、二、三”之后的空白行,而输出总共有 11 行,包括“黄色、红色”之后的一个空白行和“三、二、一”之后的两个空白行”。获得完全正确的格式至关重要,因为测试将是自动化的并且需要这种格式。另请注意,每个问题的输出行的顺序并不重要。这意味着输出的前两行也可能是:


这是我到目前为止的代码......我已经评论了一些东西所以不要担心那些部分

0 投票
5 回答
878 浏览

c# - 数组列表对象的排列

我有一个包含一些对象的数组列表,我必须得到这些对象的排列?我该怎么做?假设 MyList 是一个包含 4 个对象的数组列表。

所以arraylist计数是4所以我想要4!= 24我想要那个对象的24个排列。我怎么能在 C# 中做到这一点。请帮助我。

谢谢!

0 投票
13 回答
42530 浏览

python - 有效地计算组合和排列

我有一些代码来计算排列和组合,并且我正在努力让它更好地适用于大量数字。

我找到了一种更好的排列算法,可以避免大的中间结果,但我仍然认为我可以在组合方面做得更好。

到目前为止,我已经放入了一个特殊情况来反映 nCr 的对称性,但我仍然想找到一个更好的算法来避免调用 factorial(r),这是一个不必要的大中间结果。如果没有这种优化,最后一个 doctest 会花费很长时间来计算阶乘(99000)。

任何人都可以提出一种更有效的计算组合的方法吗?

0 投票
4 回答
2221 浏览

c# - 检索树结构的所有排列的有效方法

为更大的树编辑,以获取更多示例。

我有一个树结构,我需要生成所有可能的排列,但有一些限制。给定一棵这样的树:

或者,如果这有点模糊,这里是使用 Perl 表示法完成的相同结构:

(坦率地说,如果你能在可读的Perl 中解决这个问题,我也会接受。)

我正在寻找遍历树并从顶层向下检索所有可能的“路径”。一个节点的所有后代组必须由“路径”中的 1 个成员表示。例如,在 A1 中,需要表示 (B1, B2) 之一和 (C1) 之一。因此,从 A1 下降的每条路径都将从以下任一开始:

A1 B1 C1

或者

A1 B2 C1

如果 B1、B2 或 C1 有孩子,则也需要代表这些孩子。

为上面的树手动解决这个问题,我得到了这些可能性:

这里的每个节点都是一个 DataRow 对象:

要构建上面的示例树(E 和 F 级别除外,稍后添加):

走整棵树是微不足道的:

但这不是我需要的。这个问题是一个完整的树遍历,但是按照特定的顺序。我没有得到什么?这是一种怎样的步行方式?

我在 10 年前用 Perl 编写的这个实现混乱而缓慢,但我不能再破译我自己的代码了(真丢脸!)。

编辑:下面的图表和列表已经扩展,代码没有。

如果我能描述图表,我就可以对其进行编程。如果我知道它叫什么,我可以查一下。但我不能。所以让我进一步解释一下。

存储桶名称并不重要!

每个节点都有“孩子的桶”。A1 有两个桶,一个包含“B”,另一个包含“C”。如果这就是它的全部(并且 C 下没有存储桶),我将拥有“A1 B1 C1”和“A1 B2 C1”——所有子存储桶中至少有一个代表存在。

所以我认为每个桶都需要它的孩子的叉积(一直向下)。