给定具有n个元素的集合C(允许重复)和n
P = {i1,i2,.../i1 + i2 + ... = n} 的分区P 在大小为i1,i2的子集中有多少不同的C分解, ... 在那儿 ？
示例:
C = {2 2 2 3}
P = {2 2}
C = {2 2} U {2 3}
P = {1 1 2}
C = {2} U {2} U {2 3}
C = {2} U {3} U {2 2}
P = {1 3}
C = {2} U {2 2 3}
C = {3} U {2 2 2}
我有一个解决方案,但是当C有十几个元素时效率很低.
在此先感谢
Philippe
我认为这是一个常见的组合问题,但我似乎无法找到它的名称或任何有关它的材料.我在Python和numpy中这样做,但如果有一个快速矩阵方法,我可以翻译.
基本上,给定n个项目,我需要生成所有方法将它们放入m个箱子中.举个例子,将4个项目合并为3个区域会产生类似的结果[(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...].这是一个固定总额的产品.
使用itertools实现这一点非常简单.
import itertools
def fixed_total_product(bins, num_items):
""" Return iterator of all item binning possibilities. """
return itertools.ifilter(lambda combo: sum(combo) == num_items,
itertools.product(xrange(num_items + 1), repeat=bins))
不幸的是,我认为在循环中进行后续计算将是低效的.使用它作为2D numpy数组稍后会更快,但我无法找到一种有效的方法来构建一个数组.我可以遍历ifilter结果,构建一个可能性列表,并使用它来构建数组,但这似乎是一个巨大的浪费.
我猜这样做的最好方法是建立一切"笨拙的方式",但我不知道该怎么做.stackoverflow上有一个快速的产品实现:使用numpy构建两个数组的所有组合的数组.我猜你可以修改它只是输出正确总和的产品.数组的大小应该是((m-1)+ n)选择n,因为有m-1个bin边界.
有任何想法吗？基准非常感谢,但不是必需的.
我希望在列表中加载N个数字的组合而不重复,给予输入元素和组.例如,有4个元素[1,2,3,4],我有:
Group 1: [1][2][3][4];
Group 2: [1,2][1,3][1,4][2,3][2,4][3,4];
Group 3: [1,2,3][1,2,4][1,3,4][2,3,4]
Group 4: [1,2,3,4]
现在,我已经使用嵌套循环解决了它,例如对于组2,我写道:
for x1 := 1 to 3 do
for x2 := Succ(x1) to 4 do
begin
// x1, x2 //
end
或者对于第3组,我写道:
for x1 := 1 to 2 do
for x2 := Succ(x1) to 3 do
for x3 := Succ(x2) to 4 do
begin
// x1, x2, x3 //
end
等其他团体.一般来说,如果我想为N组做,我可以这样做,而不用嵌套循环编写N程序？我已经想到了一个双重while..do循环一个用于计数器和一个用于组计数,但所以有点难,我想知道是否有一些解决方案更简单和快速,也使用运算符布尔或其他东西.谁可以给我一些建议呢？非常感谢.
在这里,我尝试用C++编写程序来查找NCR.但是我在结果中遇到了问题.这是不正确的.你能帮我找一下程序中的错误吗？
#include <iostream>
using namespace std;
int fact(int n){
if(n==0) return 1;
if (n>0) return n*fact(n-1);
};
int NCR(int n,int r){
if(n==r) return 1;
if (r==0&&n!=0) return 1;
else return (n*fact(n-1))/fact(n-1)*fact(n-r);
};
int main(){
int n; //cout<<"Enter A Digit for n";
cin>>n;
int r;
//cout<<"Enter A Digit for r";
cin>>r;
int result=NCR(n,r);
cout<<result;
return 0;
}
我有以下问题.我需要计算一组的排列; 但是,该集合可能包含两个相同的元素,因此会导致重复的排列.例如:
给定集合[ 0 0 1 2 ],排列包括这些可能性:
1 2 0 0
1 2 0 0
但是,我想避免像这些相同的排列.在MATLAB中,我可以简单地这样做:
unique(perms([ 0 0 1 2 ]), 'rows')
但这里的问题是效率 - 我在一个巨大的for循环中反复这样做,并且所需的排序unique太慢了.所以我的问题是:我可以直接计算这种性质的独特排列,而不必在事后循环结果吗？我在MATLAB工作,但只是一个通用的解决方案可能会有所帮助,虽然可以在MATLAB中矢量化的东西可能是理想的!
据我所知,现有的问题并不能完全解决这个问题,但如果以前已经回答了这个问题,我会道歉.
考虑以下数组:
$a = [['x'], ['y', 'z', 'w'], ['m', 'n']];
如何从中生成以下数组:
$output=[
[[x][y][m]],
[[x][z][n]],
[[x][w][m]],
[[x][y][n]],
[[x][z][m]],
[[x][w][n]],
];
我正在寻找比我更有效的代码.(我目前的代码如下所示)
我正在研究免费代码营问题 - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please
问题描述如下 -
返回没有重复连续字母的提供字符串的总排列数.例如,'aab'应该返回2,因为它有6个总排列,但只有2个没有相同的字母(在这种情况下为'a')重复.
我知道我可以通过编写一个创建每个排列的程序然后过滤掉重复字符的程序来解决这个问题.
但我有这种啃咬的感觉,我可以用数学方法解决这个问题.
第一个问题 - 我可以吗？
第二个问题 - 如果是,我可以使用什么公式？
详细说明 -
问题中给出的例子是"aab",该网站称有六种可能的排列,只有两种符合非重复字符标准:
aab aba baa aab aba baa
问题是每个角色都是独特的,所以也许"aab"可以更好地描述为"a1a2b"
该问题的测试如下(返回符合标准的排列数) -
"aab" should return 2
"aaa" should return 0
"abcdefa" should return 3600
"abfdefa" should return 2640
"zzzzzzzz" should return 0
我已经阅读了很多关于组合和排列的帖子,似乎正在为自己挖掘更深的洞.但我真的想尝试有效地解决这个问题,而不是通过一系列所有可能的排列来暴力破解.
我在math.stackexchange上发布了这个问题 - https://math.stackexchange.com/q/1410184/264492
解决只重复一个字符的情况的数学非常简单 - 字符总数减去可用空格数乘以重复字符.
但试图找出重复多个字符的实例的公式却让我望而却步.例如"abfdefa"
是否有算法可以找到一系列独特元素的所有可能排列,遵循此规则？
从给定的排列中,必须通过正好循环3个元素来找到下一个排列.它们可以是任何三个元素.
对于这样的3个循环,将仅找到所有排列的子集,但是应该找到可能通过3个循环到达的所有排列,并且在找到所有可到达的排列之前不应找到相同的排列两次.
这是一个示例输入:
1,2,3,4,5
输出可能是:
3,1,2,4,5
2,3,1,4,5
4,2,1,3,5
3,4,1,2,5
1,3,4,2,5
4,1,3,2,5
2,4,3,1,5
...等
我试图产生这样一个序列的众多算法之一如下(对于数组a和长度为n):
print (a)
for i = 0 to n-1
for j = i+1 to n-1
for l = j+2 to n-1
for k = j+1 to l
cycle a[i],a[j],a[k]
print (a)
cycle a[i],a[j],a[k]
print (a)
这产生了上面印刷的系列,但接着继续:
1,2,3,4,5
..这是已经输出的排列.到目前为止我找到的任何其他寻找下一个3周期的算法都未能找到所有可达到的排列.
I have a bunch of SKUs (stock keeping units) that represent a series of strings that I'd like to create a single Regex to match for.
So, for example, if I have SKUs:
var skus = new[] { "BATPAG003", "BATTWLP03", "BATTWLP04", "BATTWSP04", "SPIFATB01" };
...I'd like to automatically generate the Regex to recognize any one of the SKUs.
I know that I could do simply do "BATPAG003|BATTWLP03|BATTWLP04|BATTWSP04|SPIFATB01", but list of SKUs can be quite lengthy and I'd like to …
我正在寻找一个计算多项系数的Python库函数.
我在任何标准库中都找不到任何这样的函数.对于二项式系数(其中多项系数是一般化),有scipy.special.binom和scipy.misc.comb.此外,numpy.random.multinomial从多项分布中抽取样本,并且sympy.ntheory.multinomial.multinomial_coefficients返回与多项式系数相关的字典.
不过,我也没有找到一个多项式系数正确发挥作用,这给A,B,...,Z回报(A + B + ... + Z)!/(A!b!... Z!).我错过了吗？有没有可用的充分理由？
我很乐意为SciPy做出有效的实施.(我必须弄清楚如何贡献,因为我从未这样做过).
对于背景,它们在扩展时会出现(a + b + ... + z)^ n.此外,他们的指望沉积的方法A + B + ... + Z不同的对象到不同的垃圾箱,使得第一箱包含一个对象,等我需要他们偶尔的项目欧拉问题.
顺便说一句,其他语言确实提供这个功能:Mathematica,MATLAB,Maple.