알고리즘 - 조합, 4 및 합계

시퀀스 사용: 1, 2, 3, 4, 5
다음 조합을 찾고 있었습니다.

원

투

쓰리

포

설명 및 예

다음 샘플에는 다음의 조합이 있습니다.

원

투

쓰리

포

조합은 열 기준입니다. 각 열은 보유한 숫자의 조합을 나타냅니다.

샘플을 하향식으로 읽으십시오.

샘플:

1
  1 2
    1 2 3
      1 2 3 4
      1 2 3 5
    1 2 4
      1 2 4 5
    1 2 5
  1 3
    1 3 4
      1 3 4 5
    1 3 5
  1 4
    1 4 5
  1 5
2
  2 3
    2 3 4
      2 3 4 5
    2 3 5
  2 4
    2 4 5
  2 5
3
  3 4
    3 4 5
  3 5
4
  4 5
5

일

각 숫자를 가져 와서 다음 각 숫자와 결합하십시오. 그런 다음 다음 번호를 선택하고 동일한 작업을 수행합니다.
하나의 조합에서 마지막 요소를 무시하십시오.

예를 들어 입력 시퀀스 A의 경우:

A[1] A[2], A[1] A[3], to A[1] A[A.length]

A[2] A[3], A[2] A[A.length]

끝까지 단계를 반복합니다.

COMBINATIONS-OF-TWO(A)
  combinations = [];
  count = 1;
  for i=1 to A.length - 1
    for j=i+1 to A.length
      combinations[count] = [i, j];
      count++;
  return combinations;

결론 및 구현

수학적 귀납법을 사용하여 우리는 다음과 같은 결론을 내립니다.

하나

하나의 조합은 배열에서 각 요소를 가져옵니다.

둘

둘의 조합은 각각 하나의 조합을 취함
그런 다음 각 후속 요소를 각각에 추가합니다.
하나의 조합에서 마지막 요소를 무시합니다.

삼

3개의 조합은 2개의 각 조합을 취합니다.
그런 다음 각 후속 요소를 각각에 추가합니다.
하나의 조합에서 마지막 2개 요소를 무시합니다.
2개의 조합에서 마지막 1개 요소를 무시합니다.

4

4개의 조합은 3개의 각 조합을 취합니다.
그런 다음 각 후속 요소를 각각에 추가합니다.
하나의 조합에서 마지막 3개 요소를 무시합니다.
2개의 조합에서 마지막 2개 요소를 무시합니다.
3개의 조합에서 마지막 1개 요소를 무시합니다.

구현

COMBINATIONS-OF-FOUR(A)
  combinations = [];
  // use counter because loops
  // don't track amount combinations
  count = 1;

  // combinations of one
  for i to A.length - 3

    // combinations of two
    for j=i+1 to A.length - 2

      // combinations of three
      for z=j+1 to A.length - 1

        // each subsequent element
        // on top of combination of three
        // gives combination of four
        for k=z+1 to A.length
          combinations[count] = [i, j, z, k];
          count++;

  return combinations;

보너스로 여기 JavaScript를 사용한 구현이 있습니다. 복사-붙여넣기 실행 가능.

function combinationsOfFour(A) {
  let combinations = [];
  let count = 0;
  let i, j, z, k;
  const len = A.length;

  for (i = 0; i < len - 3; i++) {
    for (j = i + 1; j < len - 2;j++) {
      for (z = j + 1; z < len - 1; z++) {
        for (k = z + 1; k < len; k++) {
          combinations[count] = [i, j, z, k];
          count++;
        }
      }
    }
  }

  return combinations;
}

const numbers = [0, 1, 2, 3, 4];
console.log(combinationsOfFour(numbers));

4의 유효한 합 찾기

이제 알고리즘을 수정하겠습니다. 값이 합계와 일치하는 인덱스가 있는 4배를 반환해야 합니다.

// find sums of 4 that match sum
SUMS-OF-FOUR(A, sum)
  sums = [];
  // use sum counter because loops
  // don't track amount of sums we have
  count = 1;

  // combinations of one
  for i to A.length - 3
    for j=i+1 to A.length - 2
      for z=j+1 to A.length - 1
        for k=z+1 to A.length
          // if combination of four
          // is the sum we need
          if A[i] + A[j] + A[z] + A[k] == sum
            // save the indices representing sum
            sums[count] =[i, j, z, k];
            count++;

  return sums;

얼마나 많은 루프가 필요합니까?

얼마나 많은 루프가 필요한지 알아냈습니다. 나는 내가 사용한 행동을 관찰함으로써 그렇게 했다.

시퀀스1, 2, 3, 4, 5를 사용하여 하나의 조합을 얻습니다.

1
2
3
4
5

그것은 선형이었습니다. 이제 두 가지 조합에 대해 수행하십시오.

시퀀스1, 2, 3, 4, 5를 사용하여 두 가지 조합을 얻습니다.

첫 번째 숫자:

1
  append 2 => 1, 2
  append 3 => 1, 3
  append 4 => 1, 4
  append 5 => 1, 5

두 번째 숫자:

2
  append 3 => 2, 3
  append 4 => 2, 4
  append 5 => 2, 5

루프 동작이 보이시나요? 나는 항상 그렇게하고 있었다. 내 마음이 얼마나 많은 반복을 하는지 깨닫기까지 몇 시간이 걸렸습니다.

수학적 귀납법을 사용하여 다음과 같은 결론을 내립니다.

n 조합에 대해 단계를 반복할 수 있습니다.

하나의 조합은 하나의 루프를 사용하며 선형입니다.

2개의 조합은 2개의 루프를 사용하며 2차입니다.

3개의 조합은 3개의 루프를 사용하며 입방체입니다.

유효한 r에 대한 조합 구현

시퀀스 사용1, 2, 3, 4, 5 .

레벨 3까지의 변환 또는 r=3이 주어집니다.

1
  1 2
    1 2 3
    1 2 4
    1 2 5
  1 3
    1 3 4
    1 3 5
  1 4
    1 4 5
  1 5
2
  2 3
    2 3 4
    2 3 5
  2 4
    2 4 5
  2 5
3
  3 4
    3 4 5
  3 5
4
  4 5
5

열을 레벨 또는 조합 r로 관찰할 수 있습니다. 각 조합은 이전 조합의 변환입니다. 2의 조합에 도달하기 위해 1의 각 조합을 변환합니다. 각 이전 조합에 대해 마지막 값(인덱스)을 사용합니다. 그런 다음 각 후속 인덱스를 해당 조합에 추가합니다. 그것은 우리에게 새로운 조합을 제공합니다. 후속 반복으로 동일한 양의 조합을 만듭니다. 예외는 초기 조합이며 비어 있습니다. 우리는 그것들을 채워야 합니다. 레벨당 값이 소진될 때까지 조합을 계속 변형합니다. 각 변형에 대해 하나의 수준이 필요합니다.

구현

COMBINATIONS(array, r, combinations = [])
  if combinations.length == 0
    // populate combinations of 1
    for i=1 to array.length
      combinations[i] = [i]

  if r > 1
    // next combinations
    next = []
    count = 1
    // transform each combination
    // to next one
    for i=1 to combinations.length
      // take current combination
      c = combinations[i]
      // take last index
      last = c[c.length]
      // append next indexes to
      // current combination
      for j=last+1 to array.length
        // copy current combination
        next[count] = c
        // append index to current comb.
        // which creates new one
        next[count][c.length + 1] = j
        count++

    COMBINATIONS(array, r-1, next)
  else
    return combinations

고려해야 할 제약

배열은 숫자 배열이어야 합니다.

1 <= r <= 아르곤

정보: 5개의 숫자에서 6개의 반복되지 않는 조합을 만들 수 없습니다

.

정보: 0의 조합이 의미가 없습니까?

조합은 다음 중 하나여야 합니다.

빈 배열(초기값 때문에)

숫자 배열