Problem 49803. Compute expulsions from the Kimberling shuffle

Created by ChrisR

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>The Kimberling shuffle uses a semi-infinite array of numbers in which the first row is simply the numbers 1, 2, 3, 4, 5,… Subsequent rows are generated by shuffling the previous row: the first number is the number to the right of the main diagonal of the previous row, the second is the number to the left of the main diagonal, the third is the number </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>two</w:t></w:r><w:r><w:t> slots to the right of the main diagonal, etc. When numbers run out on the left of the main diagonal, the rest of the numbers are the remaining numbers of the previous row--</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>except</w:t></w:r><w:r><w:t> for the number on the main diagonal of the previous row, which is expelled. The first few rows of the array are </w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1   2   3   4   5   6   7   8   9  10...\n2   3   4   5   6   7   8   9  10  11...\n4   2   5   6   7   8   9  10  11  12...\n6   2   7   4   8   9  10  11  12  13...\n8   7   9   2  10   6  11  12  13  14....]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Write a function to determine the row after which the input number is expelled. For example, because 5 appears on the main diagonal of row 3, your function should return 3. An optional challenge is to determine whether all numbers are eventually expelled from the array.</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; "><div style="block-size: 311.167px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 155.583px; transform-origin: 407px 155.583px; vertical-align: baseline; "><div style="block-size: 126px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 63px; text-align: left; transform-origin: 384px 63px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 368.983px 7.79167px; transform-origin: 368.983px 7.79167px; unicode-bidi: normal; "><span style="">The Kimberling shuffle uses a semi-infinite array of numbers in which the first row is simply the numbers 1, 2, 3, 4, 5,… Subsequent rows are generated by shuffling the previous row: the first number is the number to the right of the main diagonal of the previous row, the second is the number to the left of the main diagonal, the third is the number </span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 10.8917px 7.79167px; transform-origin: 10.8917px 7.79167px; unicode-bidi: normal; "><span style="font-style: italic; ">two</span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 26.05px 7.79167px; transform-origin: 26.05px 7.79167px; unicode-bidi: normal; "><span style=""> slots to the right of the main diagonal, etc. When numbers run out on the left of the main diagonal, the rest of the numbers are the remaining numbers of the previous row--</span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 20.6167px 7.79167px; transform-origin: 20.6167px 7.79167px; unicode-bidi: normal; "><span style="font-style: italic; ">except</span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 235.725px 7.79167px; transform-origin: 235.725px 7.79167px; unicode-bidi: normal; "><span style=""> for the number on the main diagonal of the previous row, which is expelled. The first few rows of the array are </span></span></div><div style="background-color: rgb(247, 247, 247); block-size: 102.167px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404px 51.0833px; transform-origin: 404px 51.0833px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; "><div style="background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.916667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.916667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.916667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.916667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 154px 8.25px; transform-origin: 154px 8.25px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; ">1   2   3   4   5   6   7   8   9  10...</span></span></div><div style="background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.916667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.916667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.916667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.916667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 154px 8.25px; transform-origin: 154px 8.25px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; ">2   3   4   5   6   7   8   9  10  11...</span></span></div><div style="background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.916667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.916667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.916667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.916667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 154px 8.25px; transform-origin: 154px 8.25px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; ">4   2   5   6   7   8   9  10  11  12...</span></span></div><div style="background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.916667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.916667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.916667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.916667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 154px 8.25px; transform-origin: 154px 8.25px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; ">6   2   7   4   8   9  10  11  12  13...</span></span></div><div style="background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.916667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.916667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.916667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.916667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 157.85px 8.25px; transform-origin: 157.85px 8.25px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; perspective-origin: 146.3px 8.25px; transform-origin: 146.3px 8.25px; ">8   7   9   2  10   6  11  12  13  14.</span><span style="border-block-end-color: rgb(14, 0, 255); border-block-start-color: rgb(14, 0, 255); border-bottom-color: rgb(14, 0, 255); border-inline-end-color: rgb(14, 0, 255); border-inline-start-color: rgb(14, 0, 255); border-left-color: rgb(14, 0, 255); border-right-color: rgb(14, 0, 255); border-top-color: rgb(14, 0, 255); caret-color: rgb(14, 0, 255); color: rgb(14, 0, 255); column-rule-color: rgb(14, 0, 255); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(14, 0, 255); perspective-origin: 11.55px 8.25px; text-decoration: none; text-decoration-color: rgb(14, 0, 255); text-emphasis-color: rgb(14, 0, 255); transform-origin: 11.55px 8.25px; ">...</span></span></div></div><div style="block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 369.008px 7.79167px; transform-origin: 369.008px 7.79167px; unicode-bidi: normal; "><span style="">Write a function to determine the row after which the input number is expelled. For example, because 5 appears on the main diagonal of row 3, your function should return 3. An optional challenge is to determine whether all numbers are eventually expelled from the array.</span></span></div></div></div>

Solve

Solution Stats

2 Solutions
2 Solvers

Last Solution submitted on Jan 11, 2021

Last 200 Solutions

Problem Recent Solvers2

Problem Tags

sequences

Community Treasure Hunt

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

Start Hunting!

Problem 49803. Compute expulsions from the Kimberling shuffle

Solution Stats

Last 200 Solutions

Problem Recent Solvers2

Suggested Problems

More from this Author135

Problem Tags

Community Treasure Hunt

Problem 49803. Compute expulsions from the Kimberling shuffle

Solution Stats

Last 200 Solutions

Problem Recent Solvers2

Suggested Problems

More from this Author135

Problem Tags

Community Treasure Hunt

Players