草庐IT

php - 编写更快的组合算法

coder 2024-04-10 原文

我正在尝试编写一个组合算法，以在不重复的情况下从 n 中获取 k 的所有可能组合。

公式为:

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

这是完成此任务的最快方法吗？有没有办法加快速度？也许递归地写它？

最佳答案

我认为问题是计算 C(n,k) 可以在不计算阶乘的情况下完成，诀窍是首先注意

C(n,k) = (n*(n-1)...(n-k+1)) / (1*2*...*k) = (n/1)*(n-1/2)*...(n-k+1/k)

也为了效率

C(n,k) = C(n,n-k), therefore choose which ever is smaller k or n-k

如果有错误，请随意编辑，因为我是从 C 语言转换过来的，我不懂 php

function nCk($n, $k)
{
    if( $n-$k<$k )
        $k = $n-$k;
    $ans = 1;
    for( $i=1; $i<=$k; ++$i )
    {
        $ans = ($ans*($n-$i+1))/$i;
    }
    return $ans;
}

关于php - 编写更快的组合算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8650327/

编写phpcodesectionFactorialalgorithmrecursioncombinatorics

有关php - 编写更快的组合算法的更多相关文章

  1. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  2. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. ruby-on-rails - 如何为空白字段编写 rspec？ [Rails3.1] - 2

    我使用rails3.1+rspec和factorygirl。我对必填字段(validates_presence_of)的验证工作正常。我如何让测试将该事实用作“成功”而不是“失败”规范是:describe"Addanindustrywithnoname"docontext"Unabletocreatearecordwhenthenameisblank"dosubjectdoind=Factory.create(:industry_name_blank)endit{shouldbe_invalid}endend但是我失败了:Failures:1)Addanindustrywithnona

  5. ruby - 最多 n 的组合 - 2

    给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我

  6. ruby - 如何更快地解决 project euler #21？ - 2

    原始问题Letd(n)bedefinedasthesumofproperdivisorsofn(numberslessthannwhichdivideevenlyinton).Ifd(a)=bandd(b)=a,whereab,thenaandbareanamicablepairandeachofaandbarecalledamicablenumbers.Forexample,theproperdivisorsof220are1,2,4,5,10,11,20,22,44,55and110;therefored(220)=284.Theproperdivisorsof284are1,2,

  7. ruby - Rails 组合多个 activerecord 关系 - 2

    我想合并多个事件记录关系例如，apple_companies=Company.where("namelike?","%apple%")banana_companies=Company.where("namelike?","%banana%")我想结合这两个关系。不是合并，合并是apple_companies.merge(banana_companies)=>Company.where("namelike?andnamelike?","%apple%","%banana%")我要Company.where("名字像？还是名字像？","%apple%","%banana%")之后，我会写代

  8. ruby-on-rails - 尝试为 Rails 中的用户名验证编写 REGEX - 2

    我正在尝试用Ruby(Rails)编写一个正则表达式，以便用户名的字符仅包含数字和字母(也没有空格)。我有这个正则表达式，/^[a-zA-Z0-9]+$/，但它似乎没有用，我在Rails中收到一个错误，说“The如果正则表达式使用多行anchor(^或$)，这可能会带来安全风险。您是要使用\A和\z，还是忘记添加:multiline=>true选项？"我的user.rb模型中此实现的完整代码是:classUser我做错了什么以及如何修复此正则表达式，使其仅对数字和字母有效而不对空格有效？谢谢。 最佳答案 简短回答:使用/\A[a-z

  9. ruby-on-rails - 如何编写跨模型、 Controller 和 View 的 Rails mixin - 2

    为了减少我的小Rails应用程序中的代码重复，我一直致力于将我的模型之间的通用代码放入它自己的单独模块中，到目前为止一切顺利。模型的东西相当简单，我只需要在开头包含模块，例如:classIso这工作正常，但是现在，我将有一些Controller和View代码，这些代码也将在这些模型之间通用，到目前为止，我有这个用于我的可发送内容:#Thisisamodulethatisusedforpages/formsthatarecanbe"sent"#eitherviafax,email,orprinted.moduleSendablemoduleModeldefself.included(kl

  10. ruby - 如何在 ruby 中组合/排列？ - 2

    我有一个熟悉的问题，看起来像是数学世界的排列/组合。如何通过ruby​​实现以下目标？badges="1-2-3"badge_cascade=[]badges.split("-").eachdo|b|badge_cascade["1","2","3"]ButIwantittobeis:=>["1","2","3","1-2","2-3","3-1","2-1","3-2","1-3","1-2-3","2-3-1","3-1-2"] 最佳答案 函数式方法:bs="1-2-3".split("-")strings=1.upto(bs.

随机推荐