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

28 Solutions
18 Solvers

Last Solution submitted on Jul 18, 2020

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 at 16:40

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 at 16:55

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

Problem Recent Solvers18

Problem Tags

combinations speed optimization

Problem 44241. NCHOOSEK - Time Optimization

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers18

Suggested Problems

More from this Author8

Problem Tags

Problem 44241. NCHOOSEK - Time Optimization

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers18

Suggested Problems

More from this Author8

Problem Tags

Players