[JavaScript]コンビネーション、シーケンス、再帰(再帰)
21646 ワード
プログラマメニューの更新の問題に答えようとします.
コンビネーションを使用して問題を解決すべきだと知っていますが、コンビネーションを実現するコードを生成することはできません.
ソース:コードテスト練習-メニュー更新|プログラマー
1.組み合わせ(組み合わせ)
再帰関数の学習に適したブログ
Chapter 1. 回帰:概念と基本例-生涯学習ブログ:Today I Learned‐🌙 ソース:[JS]シーケンス、組み合わせと繰り返しシーケンスを求める
JavaScriptを使用してシーケンスと組合せアルゴリズムを実装します。再帰、JavaScript Array Methods|byダンスの開発者|Medium
JavaScriptによるシーケンスと組合せアルゴリズムの実装
コンビネーションを使用して問題を解決すべきだと知っていますが、コンビネーションを実現するコードを生成することはできません.
ソース:コードテスト練習-メニュー更新|プログラマー
1.組み合わせ(組み合わせ)
再帰関数を使用して実装できます.
再帰関数は見苦しい
ゆっくり読むとわかるけど、実現させてもらえたら、できない気がする.
ブログ検索により,組合せとソートの実現方法を理解した.ありがとう!
基本的な考え方
시작
1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
[1, 2, 3] [1, 2, 4] [1, 3, 4]
2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
[2, 3, 4]
3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다.
[]
4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
[]
종료
上記の一連のプロセスにより、すべての組合せを見つけることができる.
入力された入力シーケンスが長くなるかどうかにかかわらず、組み合わせる必要がある要素が増加します.
アレイの最初から1つ1つ固定して、残りのアレイを組み合わせて、貼り付けるだけでいいです...
再帰関数を使用するには、繰り返し続けること(組み合わせを求めるコード)を明確にし、入力したパラメータ(私以外)を変更するだけです.
再帰関数の実装
19615;再帰終了条件:1つを選択した場合、すべての配列の要素を選択して返します.
2▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼\9660
3固定(固定)値の残りの配列について,組合せを求める.このとき,1つの選択の数を減らす.
4則は、生成された結果に固定された値を加算し、返される配列に展開構文を使用して並べ替え、返されます.
5▼▼▼2 C 3、1 C 2など選択した個数が多ければ多いほど空の配列が返されるので、上記の例では3と4を選択すると空の配列が返され、最終結果値には含まれません. const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
// 해당하는 fixed를 제외한 나머지 뒤
const combinations = getCombinations(rest, selectNumber - 1);
// 나머지에 대해서 조합을 구한다.
const attached = combinations.map((el) => [fixed, ...el]);
// 돌아온 조합에 떼 놓은(fixed) 값 붙이기
results.push(...attached);
// 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
};
2.配列(置換)
順番が大切です.
fixedも同様に返されますが、結合する残りの配列の設定が異なる場合は、上記の組合せ実装を参照して簡単に実現できます.function permutation(arr, selectNum) {
let result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixer = v;
const restArr = arr.filter((_, index) => index !== idx);
const permuationArr = permutation(restArr, selectNum - 1);
const combineFixer = permuationArr.map((v) => [fixer, ...v]);
result.push(...combineFixer);
});
return result;
};
3.問題を解く function solution(orders, course) {
var answer = [];
var orderBox = [];
function combination(arr, selectNum) {
const result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixed = v;
const restArr = arr.slice(idx + 1);
const combinationArr = combination(restArr, selectNum - 1);
const combineFix = combinationArr.map((v) => [fixed, ...v]);
result.push(...combineFix);
});
return result;
}
course.forEach(course => {
orders.forEach(order => {
const food = combination(order.split(''), course).map(order => {
return order.sort().join('');
})
orderBox.push(...food);
})
const candidate = orderBox.reduce((acc, cur) => {
acc[cur] = (acc[cur] || 0) + 1;
return acc;
}, {});
let maxOrderFood = [];
let maxOrder = 0;
for (let key in candidate) {
if (maxOrder < candidate[key]) {
maxOrderFood = [key];
maxOrder = candidate[key];
} else if (maxOrder === candidate[key]) {
maxOrderFood.push(key);
}
}
if (maxOrder >= 2) answer.push(...maxOrderFood);
orderBox = [];
})
answer.sort();
return answer;
}
시작
1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
[1, 2, 3] [1, 2, 4] [1, 3, 4]
2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
[2, 3, 4]
3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다.
[]
4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
[]
종료
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
// 해당하는 fixed를 제외한 나머지 뒤
const combinations = getCombinations(rest, selectNumber - 1);
// 나머지에 대해서 조합을 구한다.
const attached = combinations.map((el) => [fixed, ...el]);
// 돌아온 조합에 떼 놓은(fixed) 값 붙이기
results.push(...attached);
// 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
};
順番が大切です.
fixedも同様に返されますが、結合する残りの配列の設定が異なる場合は、上記の組合せ実装を参照して簡単に実現できます.
function permutation(arr, selectNum) {
let result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixer = v;
const restArr = arr.filter((_, index) => index !== idx);
const permuationArr = permutation(restArr, selectNum - 1);
const combineFixer = permuationArr.map((v) => [fixer, ...v]);
result.push(...combineFixer);
});
return result;
};
3.問題を解く function solution(orders, course) {
var answer = [];
var orderBox = [];
function combination(arr, selectNum) {
const result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixed = v;
const restArr = arr.slice(idx + 1);
const combinationArr = combination(restArr, selectNum - 1);
const combineFix = combinationArr.map((v) => [fixed, ...v]);
result.push(...combineFix);
});
return result;
}
course.forEach(course => {
orders.forEach(order => {
const food = combination(order.split(''), course).map(order => {
return order.sort().join('');
})
orderBox.push(...food);
})
const candidate = orderBox.reduce((acc, cur) => {
acc[cur] = (acc[cur] || 0) + 1;
return acc;
}, {});
let maxOrderFood = [];
let maxOrder = 0;
for (let key in candidate) {
if (maxOrder < candidate[key]) {
maxOrderFood = [key];
maxOrder = candidate[key];
} else if (maxOrder === candidate[key]) {
maxOrderFood.push(key);
}
}
if (maxOrder >= 2) answer.push(...maxOrderFood);
orderBox = [];
})
answer.sort();
return answer;
}
function solution(orders, course) {
var answer = [];
var orderBox = [];
function combination(arr, selectNum) {
const result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixed = v;
const restArr = arr.slice(idx + 1);
const combinationArr = combination(restArr, selectNum - 1);
const combineFix = combinationArr.map((v) => [fixed, ...v]);
result.push(...combineFix);
});
return result;
}
course.forEach(course => {
orders.forEach(order => {
const food = combination(order.split(''), course).map(order => {
return order.sort().join('');
})
orderBox.push(...food);
})
const candidate = orderBox.reduce((acc, cur) => {
acc[cur] = (acc[cur] || 0) + 1;
return acc;
}, {});
let maxOrderFood = [];
let maxOrder = 0;
for (let key in candidate) {
if (maxOrder < candidate[key]) {
maxOrderFood = [key];
maxOrder = candidate[key];
} else if (maxOrder === candidate[key]) {
maxOrderFood.push(key);
}
}
if (maxOrder >= 2) answer.push(...maxOrderFood);
orderBox = [];
})
answer.sort();
return answer;
}
Chapter 1. 回帰:概念と基本例-生涯学習ブログ:Today I Learned‐🌙
JavaScriptを使用してシーケンスと組合せアルゴリズムを実装します。再帰、JavaScript Array Methods|byダンスの開発者|Medium
JavaScriptによるシーケンスと組合せアルゴリズムの実装
Reference
この問題について([JavaScript]コンビネーション、シーケンス、再帰(再帰)), 我々は、より多くの情報をここで見つけました https://velog.io/@effort_jk/JavaScript-조합과-순열テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol