1 | 'use strict'
|
2 |
|
3 | const flatten = require('../../utils/array').flatten
|
4 |
|
5 | function factory (type, config, load, typed) {
|
6 | const MatrixIndex = load(require('../../type/matrix/MatrixIndex'))
|
7 | const size = load(require('../matrix/size'))
|
8 | const subset = load(require('../matrix/subset'))
|
9 | const compareNatural = load(require('../relational/compareNatural'))
|
10 |
|
11 | |
12 |
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 |
|
30 | const setPowerset = typed('setPowerset', {
|
31 | 'Array | Matrix': function (a) {
|
32 | if (subset(size(a), new MatrixIndex(0)) === 0) {
|
33 | return []
|
34 | }
|
35 | const b = flatten(Array.isArray(a) ? a : a.toArray()).sort(compareNatural)
|
36 | const result = []
|
37 | let number = 0
|
38 | while (number.toString(2).length <= b.length) {
|
39 | result.push(_subset(b, number.toString(2).split('').reverse()))
|
40 | number++
|
41 | }
|
42 |
|
43 | return _sort(result)
|
44 | }
|
45 | })
|
46 |
|
47 | return setPowerset
|
48 |
|
49 |
|
50 | function _subset (array, bitarray) {
|
51 | const result = []
|
52 | for (let i = 0; i < bitarray.length; i++) {
|
53 | if (bitarray[i] === '1') {
|
54 | result.push(array[i])
|
55 | }
|
56 | }
|
57 | return result
|
58 | }
|
59 |
|
60 |
|
61 | function _sort (array) {
|
62 | let temp = []
|
63 | for (let i = array.length - 1; i > 0; i--) {
|
64 | for (let j = 0; j < i; j++) {
|
65 | if (array[j].length > array[j + 1].length) {
|
66 | temp = array[j]
|
67 | array[j] = array[j + 1]
|
68 | array[j + 1] = temp
|
69 | }
|
70 | }
|
71 | }
|
72 | return array
|
73 | }
|
74 | }
|
75 |
|
76 | exports.name = 'setPowerset'
|
77 | exports.factory = factory
|