Próbuję policzyć liczbę liczb wyrażoną przez liczbę P 1 i 0 w formie binarnej. Jeśli p = 2, to numery są wyrażone 0011, 1100, 0110, 0101, 1001, 1010, dzięki czemu liczba wynosi 6.Najlepszy algorytm liczenia permutacji w rubinie
że próbował:
[0,0,1,1].permutation.to_a.uniq
jednak nie jest najlepszym rozwiązaniem duże liczby (P może być < = 30).
Co może być najlepszą techniką permutacji, czy też mamy jakąś prostą matematykę, aby to zrobić?
Number of permutation can be calculated using factorial.
a = [0, 0, 1, 1]
(1..a.size).inject(:*) # => 4! => 24
liczyć powielony element, trzeba podzielić powyżej 2! i 2! (2 => Liczba 0s, 1 s)
=>4!/(2! * 2!) => 6
class Fixnum
def factorial
(1..self).inject(:*)
end
end
a.size.factorial/a.group_by(&:itself).map { |k, v| v.size.factorial }.inject(:*)
=> 6
dla danego p, nie (p*2)! permutacji/i powinny być podzielone przez (p! * p!) usunąć powielanie:
p = 2
(p*2).factorial/(p.factorial ** 2)
# => 6
Spektakularne czytniki: dla p = 3 wyobraź sobie, że 1 (0) są czarne (biały) bloki ponumerowane 1, 2 i 3. 6 bloków można zamówić 6! sposoby. Teraz rozważ jeden z tych 6! uporządkowania (np. w3, b1, b3, w1, w2, b2). Jeśli zależy nam tylko na porządkowaniu kolorów, możemy zapytać, na ile sposobów można blokować czarne bloki w tej sekwencji. Istnieją 3 sposoby wyboru pierwszego bloku, a dla każdego z nich istnieją dwa sposoby zamawiania dwóch pozostałych czarnych bloków. Dlatego są 3! = 6 uporządkowanych kolorystycznie porządków czarnych bloków ... –
... Dla każdego z tych zamówień są 3! zachowujące kolor porządki białych bloków. Stąd dla danej sekwencji 6 bloków są 3! * 3! zachowujące kolory uporządkowania bloków, dlatego falsetru podzielone (2p)! przez p! * p! w celu uzyskania pożądanej liczby permutacji. –
@CarySwoveland, Dzięki za uprzejme wyjaśnienie! – falsetru
Jak dziesiętny ma znaczenie dla twojego problemu? To nie wygląda tak, jak jest. – sawa
W jaki sposób fakt, że P może być równy lub mniejszy niż 30, wpływa na obliczenia związane z uzyskiwaniem dużych liczb? Czy to nie jest poważne, kiedy P staje się duże? – sawa
@sawa druga część pytania zawiera ograniczenie dziesiętne A, B. E.g. musimy wydrukować liczbę na podstawie danego zakresu A, B. Na przykład. dla tego samego przykładu A = 5, B = 10, P = 2, wtedy mam tylko 4 wartości w tym zakresie (z wyjątkiem 3 i 12) – Yusuf