Какой алгоритм может рассчитать набор мощности данного набора?
Я знаю, что это старый вопрос, но он хотел дать дополнительный вариант.
jQuery Globalize дает возможность анализировать формат, специфичный для культуры, для поплавка.
https://github.com/jquery/globalize
С учетом строки «$ 13 042,00» и «Глобализация» установлена в en-US:
Globalize.culture("en-US");
Вы можете разобрать значение float так:
var result = Globalize.parseFloat(Globalize.format("$13,042.00", "c"));
Это даст вам:
13042.00
И позволяет вам работать с другими культурами ,
2 ответа
Есть название для того, о чем вы спрашиваете. Это называется силовое множество.
Гугление по запросу "power set algorithm" привело меня к этому рекурсивному решению.
Алгоритм Ruby
def powerset!(set)
return [set] if set.empty?
p = set.pop
subset = powerset!(set)
subset | subset.map { |x| x | [p] }
end
Интуиция множества мощности
Если S = (a, b, c), то powerset(S) - это множество всех подмножеств. powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
Первый "фокус" заключается в попытке определить рекурсивно.
Что будет состоянием остановки?
S = () имеет какой powerset(S)?
Как добраться до него?
Уменьшить множество на один элемент
Рассмотрите возможность удаления элемента - в примере выше удалите {c}
S = (a,b), тогда powerset(S) = {(), (a), (b), (a,b)}
Чего не хватает?
powerset(S) = {(c), (a,c), (b,c), (a,b,c)}
хммм
Заметили сходство? Посмотрите еще раз...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
выведите любой элемент
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} is
powerset(S - {c}) = {(), (a), (b), (a,b)} объединенный с
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
где ei - элемент S (синглтон)
Псевдоалгоритм
- Переданное множество пусто? Готово (Заметим, что мощность множества {} равна {{}})
- Если нет, вынимаем элемент
- рекурсивно вызываем метод на остатке множества
- возвращаем множество, состоящее из союза из
- powerset множества без элемента (из рекурсивного вызова)
- это же множество (т.е. 2.1), но с каждым элементом в нем, объединенным с элементом, первоначально изъятым
Просто считайте от 0 до 2^n - 1 и печатайте числа в соответствии с двоичным представлением вашего счета. 1 означает, что вы печатаете это число, а 0 - нет. Example:
set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
00011 => print {1, 2}
00100 => print {3}
00101 => print {1, 3}
00110 => print {2, 3}
00111 => print {1, 2, 3}
...
11111 => print {1, 2, 3, 4, 5}