combinatorics

// Combinations and permutations.
// Counts can be verified at http://www.calculatorsoup.com/calculators/discretemathematics/permutations.php
// noprotect

'use strict'

const combinations = function (arr) {
  const result = []

  for (let i = 0; i < arr.length; i++) {
    const item1 = arr[i]

    for (let j = i + 1; j < arr.length; j++) {
      const item2 = arr[j]

      result.push([item1, item2])
    }
  }

  return result
}

const permutations = function (arr) {
  const result = []

  for (let i = 0; i < arr.length; i++) {
    const item1 = arr[i]

    for (let j = 0; j < arr.length; j++) {
      const item2 = arr[j]

      if (item1 !== item2) {
        result.push([item1, item2])
      }
    }
  }

  return result
}

const combinationsn = function (arr, n) {
  const result = []

  const indexes = []
  for (let i = 0; i < n; i++) {
    indexes.push(i)
  }

  let i = 0
  while (i < arr.length) {
    const items = []

    for (let j = 0; j < indexes.length; j++) {
      const index = indexes[j]
      items.push(arr[index])
    }

    let idx = indexes.length - 1
    let lastIndex = indexes[idx]
    while (lastIndex === arr.length - 1 && idx > 0) {
      idx--
      lastIndex = indexes[idx]
    }

    if (indexes[idx] < arr.length - 1) {
      indexes[idx]++

      let count = 0
      for (let k = idx + 1; k < indexes.length; k++) {
        indexes[k] = indexes[idx + count] + 1
        if (indexes[k] >= arr.length) {
          indexes[k] = arr.length - 1
        }
        count++
      }

      i = 0
    }

    let skip = false
    for (let k = 0; k < items.length - 1; k++) {
      for (let l = k + 1; l < items.length; l++) {
        if (items[k] === items[l]) {
          skip = true
          break
        }
      }
    }

    if (n === 1) {
      for (let k = 0; k < result.length; k++) {
        if (result[k][0] === items[0]) {
          skip = true
          break
        }
      }
    }

    if (!skip) {
      result.push(items)
    }

    i++
  }

  return result
}

const permutationsn = function (arr, n) {
  const result = []

  const indexes = []
  for (let i = 0; i < n; i++) {
    indexes.push(i)
  }

  let i = 0
  while (i < arr.length) {
    const items = []

    for (let j = 0; j < indexes.length; j++) {
      const index = indexes[j]
      items.push(arr[index])
    }

    let idx = indexes.length - 1
    let lastIndex = indexes[idx]
    while (lastIndex === arr.length - 1 && idx > 0) {
      idx--
      lastIndex = indexes[idx]
    }

    if (indexes[idx] < arr.length - 1) {
      indexes[idx]++

      for (let k = idx + 1; k < indexes.length; k++) {
        indexes[k] = 0
      }

      i = 0
    }

    let skip = false
    for (let k = 0; k < items.length - 1; k++) {
      for (let l = k + 1; l < items.length; l++) {
        if (items[k] === items[l]) {
          skip = true
          break
        }
      }
    }

    if (n === 1) {
      for (let k = 0; k < result.length; k++) {
        if (result[k][0] === items[0]) {
          skip = true
          break
        }
      }
    }

    if (!skip) {
      result.push(items)
    }

    i++
  }

  return result
}

const factorial = function (n) {
  let result = 1

  for (let i = n; i > 0; i--) {
    result *= i
  }

  return result
}

const combinationCount = function (n, k) {
  let result = 1

  let divisor = factorial(k) * factorial(n - k)
  if (divisor) {
    result = factorial(n) / divisor
  }

  return result
}

const permutationCount = function (n, k) {
  let result = 1

  let divisor = factorial(n - k)
  if (divisor) {
    result = factorial(n) / divisor
  }

  return result
}

const list = [1, 2, 3, 4, 5, 6, 7, 8]
const c = combinations(list)
console.log(c.length + ' combinations.')
console.log(c)

const p = permutations(list)
console.log(p.length + ' permutations.')
console.log(p)

for (let i = 1; i <= list.length; i++) {
  console.log(combinationsn(list, i).length === combinationCount(list.length, i))
}

for (let i = 1; i <= list.length; i++) {
  console.log(permutationsn(list, i).length === permutationCount(list.length, i))
}