Back to Repositories

Testing Combination Generation with Repetitions in javascript-algorithms

This test suite validates the combineWithRepetitions algorithm implementation, focusing on generating combinations with repeated elements from input arrays. It verifies various scenarios of combination generation with different input sizes and repetition constraints.

Test Coverage Overview

The test suite provides comprehensive coverage for the combineWithRepetitions function, testing combinations of different array sizes and repetition counts.

Tests single element arrays with single slot
Validates two-element arrays with multiple slots
Verifies three-element arrays with varying combination lengths
Confirms mathematical correctness using factorial calculations

Implementation Analysis

The testing approach employs Jest’s describe/it pattern to structure test cases systematically. Each test case validates the output array structure and content against expected combinations.

The implementation uses array comparison and length verification to ensure correct combination generation, with special attention to maintaining proper element ordering and repetition handling.

Technical Details

Testing Framework: Jest
Supporting Functions: factorial.js for mathematical validation
Test Structure: Single describe block with multiple expect assertions
Assertion Types: Array equality and length verification

Best Practices Demonstrated

The test suite exemplifies several testing best practices for algorithmic implementations.

Progressive complexity in test cases
Mathematical validation of results
Comprehensive edge case coverage
Clear test case organization
Efficient test case structuring

trekhleb/javascript-algorithms

src/algorithms/sets/combinations/__test__/combineWithRepetitions.test.js

            
import combineWithRepetitions from '../combineWithRepetitions';
import factorial from '../../../math/factorial/factorial';

describe('combineWithRepetitions', () => {
  it('should combine string with repetitions', () => {
    expect(combineWithRepetitions(['A'], 1)).toEqual([
      ['A'],
    ]);

    expect(combineWithRepetitions(['A', 'B'], 1)).toEqual([
      ['A'],
      ['B'],
    ]);

    expect(combineWithRepetitions(['A', 'B'], 2)).toEqual([
      ['A', 'A'],
      ['A', 'B'],
      ['B', 'B'],
    ]);

    expect(combineWithRepetitions(['A', 'B'], 3)).toEqual([
      ['A', 'A', 'A'],
      ['A', 'A', 'B'],
      ['A', 'B', 'B'],
      ['B', 'B', 'B'],
    ]);

    expect(combineWithRepetitions(['A', 'B', 'C'], 2)).toEqual([
      ['A', 'A'],
      ['A', 'B'],
      ['A', 'C'],
      ['B', 'B'],
      ['B', 'C'],
      ['C', 'C'],
    ]);

    expect(combineWithRepetitions(['A', 'B', 'C'], 3)).toEqual([
      ['A', 'A', 'A'],
      ['A', 'A', 'B'],
      ['A', 'A', 'C'],
      ['A', 'B', 'B'],
      ['A', 'B', 'C'],
      ['A', 'C', 'C'],
      ['B', 'B', 'B'],
      ['B', 'B', 'C'],
      ['B', 'C', 'C'],
      ['C', 'C', 'C'],
    ]);

    const combinationOptions = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'];
    const combinationSlotsNumber = 4;
    const combinations = combineWithRepetitions(combinationOptions, combinationSlotsNumber);
    const n = combinationOptions.length;
    const r = combinationSlotsNumber;
    const expectedNumberOfCombinations = factorial((r + n) - 1) / (factorial(r) * factorial(n - 1));

    expect(combinations.length).toBe(expectedNumberOfCombinations);
  });
});