我试图写一个组合数学算法得到的所有可能的组合k出来的n不重复.

公式是:

n!/(k!(n-k)!)); 

结果以数组结尾.我实际写的是这样的:

function Factorial($x)
{
    if ($x < 1)
    {
        echo "Factorial() Error: Number too small!";
    )

    $ans = 1;
    for ($xx = 2; $xx >= $x; $xx++)
    {
        $ans = $ans * $xx;
    }

    return($ans);
}

function Combination($selectcount,$availablecount)
{
    $ans = Factorial($availablecount) / (
        Factorial($availablecount - $selectcount) * Factorial($selectcount)
    );

    return ($ans);
}

这是实现这一目标的最快方法吗？有没有办法加快速度？也许以递归方式写出来？

我们应该使用什么算法来获得n位数的计数,使得其数字的乘积为p; 这里的特殊情况是没有数字应该是1;

到目前为止我所想的是对p进行素数分解.假设n = 3且p = 24.

我们首先进行24的素因数分解得到:2*2*2*3.

现在我有确定这些组合的问题

4*2*3,2*4*3,....等即使可以这样做...我将如何缩放为n小于素数的方式.

我不太确定这是否是正确的方向......欢迎提出任何意见.

问题

我妈妈是老师.她最近让我写了一个脚本,其中列出了学生名单并生成了一组学生对.每个学生都应该与其他学生配对,没有学生不止一次与同一个学生一起工作.

例如,假设她有四个学生:"Bob","Lisa","Duke"和"Tyrone".该脚本应生成以下输出:

{ { "Bob", "Lisa" }, { "Duke", "Tyrone" } }
{ { "Bob", "Duke" }, { "Lisa", "Tyrone" } }
{ { "Bob", "Tyrone" }, { "Lisa", "Duke" } }

天真的尝试

我认为这将是一个简单的项目,但我意识到编写一个有效的算法来生成列表的中途有点超出我.最初,我在Ruby中编写了这个天真的实现:

# the list of students
CLASS_LIST = ("A".."H").to_a

# add an extra element to the class list if the class list length is odd
CLASS_LIST << nil if CLASS_LIST.length.odd?

# determine all possible permutations of the class …

假设我有3个列表:['q','w'],['a','s'],['z','x'].如何从这些列表中获取可能的组合列表？所以我得到一个列表[['q','a','z'],['q','s','z']]等等.我为两个方法制作了一个方法,但是无法为N个列表找到一个方法:

static <E> ArrayList combine(ArrayList<E> one,ArrayList<E> two)
{
    ArrayList<ArrayList<E>> combs=new ArrayList<ArrayList<E>>();
    for(E e:one)
    {
        for(E e2:two)
        {
            ArrayList ps=new ArrayList();
            ps.add(e);
            ps.add(e2);
            combs.add(ps);
        }
    }
    return combs;
}

我发现这是由Guava的Sets.cartesianProduct完成的.

如何计算这个数字而不是枚举所有排列,然后创建集合以切断所有重复？

len(set(itertools.permutations('aaabbb')))
20

len(set(itertools.permutations('aabb')))
6

给定x所有子列表具有相同长度的长度列表列表y,输出包含每个子列表中的一个项目y^x的长度x列表.

示例(x = 3,y = 2):

[ [1, 2], [3, 4], [5, 6] ]

输出(2^3 == 8不同输出):

[ [1, 3, 5], [1, 4, 5], [1, 3, 6], [1, 4, 6],
  [2, 3, 5], [2, 4, 5], [2, 3, 6], [2, 4, 6] ]

我的研究/工作

红宝石

我编写了实际代码来执行此任务,但在Ruby中,因为它是我最熟悉的语言.

def all_combinations(lst)
   lst.inject {|acc, new| acc.product(new).map(&:flatten) }
end

类型

输入是包含类型a的项的列表列表,输出也是如此.

allProduct :: [[a]] -> [[a]]

笛卡尔积,扁平化和折叠

看看我的Ruby解决方案让我觉得充分利用这些功能可能足以解决问题.问题是虽然笛卡尔积输出了一个元组列表,但我需要一个列表列表.

我想要一个f获取列表列表的函数,并返回通过从每个列表中取一个元素所做的所有可能组合的元组列表.

例如

f [["A";"B";"C"];[1;2]]

会给出结果:

[("A",1);("A",2);("B",1);("B",2);("C",1);("C",2)]

和:

f [[onions;peas];[mash;fries];[chicken;steak]]

会给:

[(onions,mash,chicken);(onions,mash,steak);(onions;fries;chicken) ... (peas,fries,steak)]

我正在考虑滚动我自己,但感觉必须有一个库函数比我的拇指拳法更好地优化,但我似乎无法通过谷歌搜索找到任何东西(我可能不知道正确的组合术语,所以保持打不同的组合方法和功能)

假设我有一套A={a_1, a_2, ..., a_n}.我还有一个f:AxA->R从A某个实际值中分配一对的函数.我想提取一个子集S_k的大小k 从A以使其最大程度地提高所有元素的整体成对总和S_k

是否有任何已知的算法可以在合理的时间内完成此操作？多项式/准多项式时间也许？

编辑:工作示例

假设A={a_1,a_2,a_3,a_4}with k=3和f定义为:

f(a_1,a_2)=0,f(a_1,a_3)=0,f(a_1,a_4)=0,f(a_2,a_3)=1,f(a_2,a_4)=5,f(a_3,a_4)=10.

然后,S_k={a_2,a_3,a_4}因为它最大化总和f(a_2,a_3)+f(a_2,a_4)+f(a_3,a_4).(即S_k中所有元素的成对总和)

我正在寻找一组数字，并旨在通过集合分区将它们分成子集。如何生成这些子集的决定因素是确保子集中所有元素的总和尽可能接近由预定分布生成的数字。子集的大小不必相同，每个元素只能在一个子集中。我之前已经通过贪心算法（链接在这里）获得了关于这个问题的指导，但我发现集合中的一些较大的数字大大扭曲了结果。因此，我想对这个问题使用某种形式的集合分区。

一个更深层次的潜在问题，我真的很想纠正未来的问题，我发现我被这些类型问题的“蛮力”方法所吸引。（正如您从我下面的代码中看到的，该代码尝试使用折叠通过“蛮力”来解决问题）。这显然是一种完全低效的解决问题的方法，所以我想用更智能的方法来解决这些最小化类型的问题。因此，非常感谢任何建议。

library(groupdata2)
library(dplyr)

set.seed(345)
j <- runif(500,0,10000000)
dist <- c(.3,.2,.1,.05,.065,.185,.1)
s_diff <- 9999999999

for (i in 1:100) {
    x <- fold(j, k = length(dist), method = "n_rand")

    if (abs(sum(j) * dist[1] - sum(j[which(x$.folds==1)])) < abs(s_diff)) {
        s_diff <- abs(sum(j) * dist[1] - sum(j[which(x$.folds==1)]))
        x_fin <- x
    }
}

这只是一个仅查看第一个“子集”的简化版本。s_diff将是模拟的理论和实际结果之间的最小差异，并且x_fin是每个元素将在哪个子集中（即它对应于哪个折叠）。然后我想删除落入第一个子集的元素并从那里继续，但我知道我的方法效率低下。

提前致谢！

我参加了 CodeSignal 练习考试，并且能够通过 14/16 测试用例来解决这个问题。您将获得一个向量作为输入（整数列表），并且解决方案将很长很长。

最初我只是使用了两个 for 循环的蛮力解决方案，并将当前的 a[i] concat a[j] 添加到运行总数中。但是，我尝试通过使用记忆来优化它。我使用 unordered_map 对检查我是否已经计算了 (i,j) 对，如果已经计算，只需返回缓存的结果。即使进行了优化，我仍然没有通过任何额外的测试用例并收到 14/16 的结果。我缺少什么见解或优化？

我发现了类似的在线问题，但是他们的见解似乎不适用于这个特定问题。

例如：类似问题

题：

给定一个正整数数组a，您的任务是计算每个可能的 concat(a[i], a[j]) 的总和，其中 concat(a[i],a[j]) 是字符串的串联分别表示 a[I] 和 a[j]。

前任：

a = [10,2]
sol = 1344
a[0],a[0] = 1010
a[0],a[1] = 102
a[1],a[0] = 210
a[1],a[1] = 22
sum of above = 1344

代码：

long long concat(int x, int y)
{
  string str = to_string(x)+to_string(y);
  return stoll(str);
}
long long calculateSum(vector<int> a)
{
  unordered_map<pair<int,int>,long long, hash_pair> …