Created
July 13, 2018 12:15
-
-
Save foobic/5de8a8396619454f5aad40a5b0bffdb5 to your computer and use it in GitHub Desktop.
Задача 108: Теория множеств. Дано множество, состоящее из N элементов, его элементы - все числа от 1 до N включительно. Необходимо определить кол-во всевозможных подмножеств заданного множества, а также вывести все эти подмножества (пустое множество можно не выводить).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Идея такая: | |
// Рекурсивно с помощью операции симметрической разницы строим из заданных элементов множества всевозможноные комбинации на основе уже имеющихся. | |
// Например: Дано множество [1,2,3] | |
// 1. [1,2,3] длина = 3 | |
// 2. Получаем всевозможные подмножества длиной=2 с помощою результата симметрической разницы между заданным множетсвом и его элементами | |
// [1,2,3] - [1] = [2,3] , [1,2,3] - [2] = [1,3], [1,2,3] - [3] = [1,2] | |
// 3. Выполняем пункт 2 для полученных подмножеств до тех пор пока n > 1 | |
// Ф-я удаления дублирующихся элементов из массива через Set | |
// В том числе сравниваются по значениям и удаляются одинаковые массивы в массиве. | |
let removeDuplicatesEs6 = arr => Array.from(new Set(arr.map(JSON.stringify)), JSON.parse); | |
// Ф-я которая реализует операцию симметрической разницы двух множеств | |
let symDiff = (arr1, arr2) => { | |
let result = arr1.filter(el => arr2.indexOf(el) ===-1 ? true : false) | |
result = result.concat(arr2.filter(el => arr1.indexOf(el) ===-1 ? true : false)) | |
return removeDuplicatesEs6(result); | |
} | |
// рекурсивная функция, которая находит все подмножества | |
// 1-й параметр - N | |
// 2-й параметр - Заданное множество | |
// 3-й параметр - ссылка на обьект результата | |
function task108(n, arr, result){ | |
if(n !== arr.length) return false // Если N != длине заданного множества - ошибка | |
if(result.arr.length === 0 ) { | |
// Проверка елементов множества. Елментами множества должны быть | |
// натуральные числа от 1 до N | |
if(arr.some(el => el > n)) return false | |
// Если в результирующем множестве ничего нет - копируем туда значения заданного множества | |
result.arr = arr.slice() | |
} | |
if(n === 1){ // условие выхода из рекурсии | |
result.arr = removeDuplicatesEs6(result.arr) // удаление дубликатов | |
return false // выход из рекурсии | |
} | |
result.arr.push(arr) // Пушим полученный массив в результат | |
arr.map(el => task108(n-1, symDiff(arr, [el]), result)) // вызываем для полученного массива эту же функцию. | |
} | |
// result - обьект для хранения результата. | |
let result = { | |
arr: [], | |
_prettyArr: function(){ // ф-я для красивого вывода подмножеств | |
this.arr = this.arr.map(el=>{ | |
if(Array.isArray(el)) return el.join("") | |
return "" + el | |
}) | |
}, | |
print: function(pretty = false){ | |
if(pretty) this._prettyArr() | |
console.log(`===\nQty of subsets: ${this.arr.length + 1}\nSubsets:`) | |
console.log(this.arr) | |
} | |
} | |
task108(5, [1,2,3,4,5], result) | |
// task108(6, [3,5,2,4,1,6], result) | |
result.print(true) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment