How to resolve the algorithm Combinations with repetitions step by step in the JavaScript programming language

Published on 12 May 2024 09:40 PM
#Javascript

How to resolve the algorithm Combinations with repetitions step by step in the JavaScript programming language

Table of Contents

Problem Statement

The set of combinations with repetitions is computed from a set,

S

{\displaystyle S}

(of cardinality

n

{\displaystyle n}

), and a size of resulting selection,

k

{\displaystyle k}

, by reporting the sets of cardinality

k

{\displaystyle k}

where each member of those sets is chosen from

S

{\displaystyle S}

. In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter. For example: Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets. Also note that doughnut can also be spelled donut.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Combinations with repetitions step by step in the JavaScript programming language

Source Code 1:

This code implements a function pick that generates combinations of items from a given list. It takes in the number of items to pick (n), an empty list to store the selected items (got), the current index in the list (pos), the list of items to choose from (from), and a flag to show the results (show).

  • It recursively iterates through the list, adding each item to the selected list and continuing the process with the remaining items.
  • If the selected list reaches the desired size, it prints the combination if show is true and returns 1 to count the combination.
  • The total number of combinations is returned.

Source Code 2:

This code implements a function combsWithRep to generate combinations with repetitions allowed.

  • The function takes two parameters: the number of items to pick (n) and the list of items to choose from (lst).
  • It recursively creates combinations by adding the first item of the list to the current combination and also by continuing the process with the remaining items in the list.
  • The result is an array of all possible combinations.

Source Code 3:

This code implements a memoized version of the combsWithRep function to improve performance, along with helper functions for memoization and range generation.

  • The memoized function takes the same parameters as combsWithRep, but it stores the results of previous calls in a memoization table.
  • This prevents redundant calculations for the same input, resulting in faster execution.

Source Code 4:

This code also implements a function combsWithRep for generating combinations with repetitions allowed.

  • The function uses a different recursive approach involving a comb function that constructs combinations by adding the first item of the list or by continuing the process with the remaining items.
  • The result is an array of all possible combinations.

Overall:

All the provided code snippets implement functions to generate combinations with repetitions allowed for varying input sizes. They differ in their implementation details, speed optimizations, and helper functions.

Source code in the javascript programming language

<html><head><title>Donuts</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
	var e = document.createTextNode(x + '\n');
	document.getElementById('x').appendChild(e);
}

function pick(n, got, pos, from, show) {
	var cnt = 0;
	if (got.length == n) {
		if (show) disp(got.join(' '));
		return 1;
	}
	for (var i = pos; i < from.length; i++) {
		got.push(from[i]);
		cnt += pick(n, got, i, from, show);
		got.pop();
	}
	return cnt;
}

disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos");
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos");
</script></body></html>


(function () {

  // n -> [a] -> [[a]]
  function combsWithRep(n, lst) {
    return n ? (
      lst.length ? combsWithRep(n - 1, lst).map(function (t) {
        return [lst[0]].concat(t);
      }).concat(combsWithRep(n, lst.slice(1))) : []
    ) : [[]];
  };

  // If needed, we can derive a significantly faster version of
  // the simple recursive function above by memoizing it

  // f -> f
  function memoized(fn) {
    m = {};
    return function (x) {
      var args = [].slice.call(arguments),
        strKey = args.join('-');

      v = m[strKey];
      if ('u' === (typeof v)[0])
        m[strKey] = v = fn.apply(null, args);
      return v;
    }
  }

  // [m..n]
  function range(m, n) {
    return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
      return m + i;
    });
  }


  return [

      combsWithRep(2, ["iced", "jam", "plain"]),

    // obtaining and applying a memoized version of the function
      memoized(combsWithRep)(3, range(1, 10)).length
    ];

})();


[
 [["iced", "iced"], ["iced", "jam"], ["iced", "plain"],
  ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]],
 220
]


(() => {
    'use strict';

    // COMBINATIONS WITH REPETITIONS -------------------------------------------

    // combsWithRep :: Int -> [a] -> [[a]]
    const combsWithRep = (k, xs) => {
        const comb = (n, ys) => {
            if (0 === n) return ys;
            if (isNull(ys)) return comb(n - 1, map(pure, xs));

            return comb(n - 1, concatMap(zs => {
                const h = head(zs);
                return map(x => [x].concat(zs), dropWhile(x => x !== h, xs));
            }, ys));
        };
        return comb(k, []);
    };

    // GENERIC FUNCTIONS ------------------------------------------------------

    // concatMap :: (a -> [b]) -> [a] -> [b]
    const concatMap = (f, xs) => [].concat.apply([], xs.map(f));

    // dropWhile :: (a -> Bool) -> [a] -> [a]
    const dropWhile = (p, xs) => {
        let i = 0;
        for (let lng = xs.length;
            (i < lng) && p(xs[i]); i++) {}
        return xs.slice(i);
    };

    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        Array.from({
            length: Math.floor(n - m) + 1
        }, (_, i) => m + i);

    // head :: [a] -> Maybe a
    const head = xs => xs.length ? xs[0] : undefined;

    // isNull :: [a] -> Bool
    const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;

    // length :: [a] -> Int
    const length = xs => xs.length;

    // map :: (a -> b) -> [a] -> [b]
    const map = (f, xs) => xs.map(f);

    // pure :: a -> [a]
    const pure = x => [x];

    // show :: a -> String
    const show = x => JSON.stringify(x, null, 2);

    // TEST -------------------------------------------------------------------
    return show({
        twoFromThree: combsWithRep(2, ['iced', 'jam', 'plain']),
        threeFromTen: length(combsWithRep(3, enumFromTo(0, 9)))
    });
})();

You may also check:How to resolve the algorithm Program termination step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Nth root step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Gapful numbers step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Soundex step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Sort an integer array step by step in the JavaScript programming language