Problem 44241. NCHOOSEK - Time Optimization

Created by LY Cao

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>V</w:t></w:r><w:r><w:t> —— Set of all choices, a vector of N, 1 &lt; N &lt; 100</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>K</w:t></w:r><w:r><w:t> —— Number of selected choices, a scalar, 0 &lt;= K &lt;= N</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Outout</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>C</w:t></w:r><w:r><w:t> —— All combinations of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>V</w:t></w:r><w:r><w:t>, equivalent to</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>nchoosek(V, K)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Time consumed</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

44 Solutions
29 Solvers

Last Solution submitted on Jun 09, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

yurenchu on 27 Jun 2017

Sorry, but it's not clear to me what the objective is. At test #3, nchoosek should accept a v that is a cell array of 30 column vectors? (What's the purpose: to present combinations per vector, or to present all cell arrays that choose a certain number of vectors?) And at test #4, nchoosek(v,1) should equal v', even when v contains duplicate entries and isn't sorted?

LY Cao on 28 Jun 2017

nchoosekFast(V,K) should have the same behavior as nchoosek(V,K) for a vector V.
you can valid:
celldisp(nchoosek({[1 2],[5 6 7],3}, 2)),
nchoosek([3 1 2 2], 1).

li haitao on 19 Nov 2018

Always return "While evaluating the solution, the server encountered an error caused by temporary unavailability of MATLAB Service. Wait a few minutes for the MATLAB Service to return, and then rescore."

Rafael S.T. Vieira on 18 Jul 2020

Maybe you should forbid the use of nchoosek? Or is the MATLAB nchoosek faster currently? It passes the last test case without changes. Moreover, nchoosek runs within 1.30 s currently for the test case at an i5-3230M CPU, 2.60GHz. That's already pretty fast.

Solution Comments

Solution 1686354

1 Comment

1 Comment

Rafael S.T. Vieira on 18 Jul 2020

This current leading solution runs within 1.40s, which is worse than the performance of regular nchoosek at my pc.

Problem Recent Solvers29

Problem Tags

combinations speed optimization

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44241. NCHOOSEK - Time Optimization

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers29

Suggested Problems

More from this Author8

Problem Tags

Community Treasure Hunt

Problem 44241. NCHOOSEK - Time Optimization

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers29

Suggested Problems

More from this Author8

Problem Tags

Community Treasure Hunt

Players