函数式实现JS/TS指定大小子集生成函数及测试方案咨询

Hey there! Let's break down how to solve this problem in a functional style with JavaScript/TypeScript, plus add proper test cases using assert.

1. Core Implementation Idea #

The key here is to use a recursive, pure function approach (no mutable state, no side effects) based on divide-and-conquer:

• For the first element in the array, we have two choices:
  1. Include it in the subset: then we need to find all subsets of size k-1 from the remaining elements, and prepend this element to each of those subsets.
  2. Exclude it from the subset: then we need to find all subsets of size k from the remaining elements.
• We combine the results of these two choices to get the final list of subsets.
• Base Cases:
  • If k === 0: Return [[]] (the only subset of size 0 is the empty subset).
  • If the input array is empty or its length is less than k: Return [] (no valid subsets exist).

2. TypeScript/JavaScript Implementation #

First, let's define the function type for TypeScript, then write the pure function:

TypeScript Version #

import assert from 'assert';

// Define the function type
type FunSubsets = (arr: number[], k: number) => number[][];

const funSubsets: FunSubsets = (arr, k) => {
  // Base case 1: k is 0, return empty subset
  if (k === 0) return [[]];
  // Base case 2: not enough elements to form k-sized subset
  if (arr.length < k) return [];

  // Split the array into first element and rest
  const [first, ...rest] = arr;

  // Choice 1: include the first element, find k-1 subsets from rest
  const withFirst = funSubsets(rest, k - 1).map(subset => [first, ...subset]);
  // Choice 2: exclude the first element, find k subsets from rest
  const withoutFirst = funSubsets(rest, k);

  // Combine both results
  return [...withFirst, ...withoutFirst];
};

JavaScript Version (No Type Annotations) #

const funSubsets = (arr, k) => {
  if (k === 0) return [[]];
  if (arr.length < k) return [];

  const [first, ...rest] = arr;
  const withFirst = funSubsets(rest, k - 1).map(subset => [first, ...subset]);
  const withoutFirst = funSubsets(rest, k);

  return [...withFirst, ...withoutFirst];
};

3. Test Cases Using assert #

Let's write 3+ test cases to verify the function works as expected. We'll use Node.js's built-in assert module:

// Test 1: Example case from the problem statement
assert.deepStrictEqual(funSubsets([1,2,3], 2), [[1,2],[1,3],[2,3]], 'Example case failed');

// Test 2: k equals the length of the array (only one subset: the array itself)
assert.deepStrictEqual(funSubsets([4,5,6], 3), [[4,5,6]], 'k equals array length failed');

// Test 3: k is 0 (only empty subset)
assert.deepStrictEqual(funSubsets([10,20], 0), [[]], 'k=0 case failed');

// Test 4: k is larger than array length (no valid subsets)
assert.deepStrictEqual(funSubsets([1,2], 3), [], 'k > array length failed');

console.log('All tests passed!');

Run these tests with Node.js, and they should all pass if the function is implemented correctly.

内容的提问来源于stack exchange，提问作者Adam Morad