72411

Generate valid combinations of numbers in array of digits

Question:

I’m trying to generate all valid combinations of numbers from an array of digits. Let’s assume we have the following:

let arr = [1, 2, 9, 4, 7];

We need to output something like this:

1 2 9 4 7 1 2 9 47 1 2 94 7 1 2 947 1 29 4 7 1 29 47 1 294 7 1 2947 12 9 4 7 12 9 47 12 94 7 12 947 129 4 7 129 47 1294 7 12947

An invalid number would be 91, 497, 72 and so on.

I tried this but I’m not satisfied with the result:

<pre class="snippet-code-js lang-js prettyprint-override">const combination = (arr) => { let i, j, temp; let result = []; let arrLen = arr.length; let power = Math.pow; let combinations = power(2, arrLen); for (i = 0; i < combinations; i += 1) { temp = ''; for (j = 0; j < arrLen; j++) { if ((i & power(2, j))) { temp += arr[j]; } } result.push(temp); } return result; } const result = combination([1, 2, 9, 4, 7]); console.log(result); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; top: 0; }

Any ideas?

Answer1:

So you need to iterate over all the combinations of "space" and "not space" between all the numbers. With n items, there will be n - 1 spaces, and 2 ** (n - 1) different lists.

So you could do something like this to get all the possible lists:

<pre class="snippet-code-js lang-js prettyprint-override">const combination = arr => { const len = arr.length; const n = Math.pow(2, len - 1); const combinations = []; for (let i = 0; i < n; i++) { let this_combination = [arr[0]]; for (let j = 1; j < len; j++) { if (i & Math.pow(2, j - 1)) { // If the jth bit is on, no space. Append to the last element. const last_index = this_combination.length - 1; this_combination[last_index] = +(this_combination[last_index] + '' + arr[j]); } else { // Otherwise create a new list item. this_combination.push(arr[j]); } } // Consider making this function a generator and making this a yield. combinations.push(this_combination); } return combinations; } const result = combination([1, 2, 9, 4, 7]); console.log(result.map(line => line.join(' ')).join('\n')); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; top: 0; }

If you wanted each individual item seperately, for each item in the array, combine it with no other item, then just the next item, then the next 2 items, etc. untill the end:

<pre class="snippet-code-js lang-js prettyprint-override">const combination = arr => { const len = arr.length; const combinations = []; for (let i = 0; i < len; i++) { let item = arr[i]; combinations.push(item); for (let j = i + 1; j < len; j++) { item = +(item + '' + arr[j]); combinations.push(item); } } return combinations; } const result = combination([1, 2, 9, 4, 7]); console.log(result.join('\n')); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer2:

This code does what you want:

<pre class="snippet-code-js lang-js prettyprint-override">const arr = [1, 2, 9, 4, 7], result = Array.from({length: 2 ** (arr.length - 1)}, (_, index) => index.toString(2).padStart(arr.length - 1, "0")) .map((binary) => JSON.parse("[" + arr.map((num, position) => num + (Number(binary[position]) ? "," : "")).join("") + "]")); console.log(result); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; top: 0; }

It results in:

[ [12947], [1294, 7], [129, 47], [129, 4, 7], [12, 947], [12, 94, 7], [12, 9, 47], [12, 9, 4, 7], [1, 2947], [1, 294, 7], [1, 29, 47], [1, 29, 4, 7], [1, 2, 947], [1, 2, 94, 7], [1, 2, 9, 47], [1, 2, 9, 4, 7] ] <hr />

Assuming, the expected result does not depend on order, the spaces represent a binary pattern:

<pre class="lang-none prettyprint-override">12947 => 0000 1294 7 => 0001 129 47 => 0010 … 1 29 47 => 1010 … 1 2 9 4 7 => 1111 <hr />

We can utilize this pattern with a counter that we convert to a binary string. We also pad that string with 0 so it always remains 4 digits long:

index.toString(2).padStart(arr.length - 1, "0")

For <em>n</em> digits in arr, there are exactly 2<sup><em>n</em> - 1</sup> combinations, so we use:

{length: 2 ** (arr.length - 1)}

This is an object that has a length property of 2<sup>arr.length - 1</sup>.

We combine both those things into an <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from" rel="nofollow">Array.from</a> call which accepts two arguments:

<ul><li>an object to turn into an array</li> <li>a function for mapping each slot</li> </ul>

Turning an object with a length property into an array means that we create an array with length many slots.

The mapping function accepts the index of a slot as the second parameter. We only use the index — as a counter for our binary number.

So, finally this whole expression:

Array.from({length: 2 ** (arr.length - 1)}, (_, index) => index.toString(2).padStart(arr.length - 1, "0"))

evaluates to the following array:

[ "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" ] <hr />

We need to further map this to the final result:

.map((binary) => …)

For each array element, binary is one of the binary strings from the array above.

In order to turn e.g. "0110" into something like "12,9,47", we need to map over arr as well. Every digit num from arr should be followed by , at position, iff binary is 1 at position:

arr.map((num, position) => num + (Number(binary[position]) ? "," : "")).join("")

The expression (Number(binary[position]) ? "," : "") evaluates binary at the specified position as a number. If it’s <em>truthy</em>, i.e. anything but 0, it evaluates to ",", if it’s <em>falsy</em>, i.e. 0, it evaluates to "".

So an intermediate array would look like ["1", "2,", "9,", "4", "7"]. All of this is joined together to "12,9,47".

Then, with JSON.parse("[" ++ "]") it’s being treated and parsed as an array, so it turns into [12, 9, 47]. Since these steps are applied for each binary string, you’ll end up with the final result.

<hr /><ul><li>2 ** (arr.length - 1) can be replaced by Math.pow(2, arr.length - 1) if ECMAScript 7 is not supported.</li> <li>{length: 2 ** (arr.length - 1)} can be replaced by new Array(2 ** (arr.length - 1)).</li> <li>(Number(binary[position]) ? "," : "") can be replaced by ["", ","][Number(binary[position])]. In this case the evaluated number will be used as an index for a temporary array.</li> </ul>

Answer3:

You could take a recursive approach by iterating the array and insert a space or not and fork the calling of the same function with an incremented index.

<pre class="snippet-code-js lang-js prettyprint-override">function combine(array) { function fork(i, p) { if (i === array.length) { result.push(p); return; } fork(i + 1, p + ' ' + array[i]); fork(i + 1, p + array[i]); } var result = []; fork(1, array[0].toString()); return result; } console.log(combine([1, 2, 9, 4, 7])); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer4:

You could do this by using below code where 3 pointer is used,

<ol><li>1st pointer print 0th position to cursor position.</li> <li>2nd pointer print cursor to diffidence position in each iteration .</li> <li>3rd pointer print cursor position to last position.</li> </ol>

<pre class="snippet-code-js lang-js prettyprint-override">let arr = [1, 2, 9, 4, 7]; console.log(arr.join(',')); for(let diff=2;diff<=arr.length;diff++){ for(i=0,j=diff;arr.length>=i+diff;j++,i++){ var temp = []; if(i>0) temp.push(arr.slice(0,i).join(',')); temp.push(arr.slice(i,j).join('')); if(j<arr.length) temp.push(arr.slice(j,arr.length).join(',')); console.log(temp.join(',')); } }

Recommend

  • C++ Reverse a smaller range in a vector
  • how to remove comments from a bash script
  • sed Removing whitespace around certain character
  • How to replace spaces at the right into zeros at the left in COBOL?
  • How to make a variable by extracting specific line?
  • Yii - Make a string usable in a URL or filename
  • Is this hack a defined behavior for T4
  • Passing and ArrayList through intent
  • UILabel extra spaces before and after text ios
  • substitute period from abbreviation (single letter + period) unless followed by a capital letter
  • Combining many rectangles into fewer rectangles
  • css font-size and line-height not matching the baseline
  • Updating and removing unique join relationships in CakePHP
  • Validate jQuery plugin, field not required
  • Azure table store snapshot/backup capability
  • Reading a file into a multidimensional array
  • wxPython: displaying multiple widgets in same frame
  • xtable package: Skipping some rows in the output
  • C: Incompatible pointer type initializing
  • why xml file does not aligned properly after append the string in beginning and end of the file usin
  • preg_replace Double Spaces to tab (\\t) at the beginning of a line
  • Change JButton Shape while respecting Look And Feel
  • Weird JavaScript statement, what does it mean?
  • Comma separated Values
  • How to delete a row from a dynamic generate table using jquery?
  • Rails 2: use form_for to build a form covering multiple objects of the same class
  • NSLayoutConstraint that would pin a view to the bottom edge of a superview
  • Error creating VM instance in Google Compute Engine
  • Hits per day in Google Big Query
  • how does django model after text[] in postgresql [duplicate]
  • Turn off referential integrity in Derby? is it possible?
  • Add sale price programmatically to product variations
  • Is there any way to bind data to data.frame by some index?
  • Django query for large number of relationships
  • Unable to use reactive element in my shiny app
  • Net Present Value in Excel for Grouped Recurring CF
  • How to push additional view controllers onto NavigationController but keep the TabBar?
  • jQuery Masonry / Isotope and fluid images: Momentary overlap on window resize
  • How to load view controller without button in storyboard?
  • How do I use LINQ to get all the Items that have a particular SubItem?