Advertisement
Guest User

Untitled

a guest
Oct 24th, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.46 KB | None | 0 0
  1. ->a{(1..a.size).flat_map{|n|a.sort.combination(n).select{|c|c.reduce(:+)==10}.uniq}}
  2.  
  3. (1..a.size) # Для диапазона от 1 до длины массива А
  4. .flat_map{ |n| # ...сконкатенировать для каждого следующее (где N текущее):
  5. a.sort # Из отсортированного массива А...
  6. .combination(n) # ...взять все комбинации длиной N элементов
  7. .select{ |c| # ...выбрав только те из них (где С текущее), в которых:
  8. c.reduce(:+)==10} # Cвёртка С сложением равна 10.
  9. .uniq} # ...убрав повторения.
  10.  
  11. sub X{my($n,%r)=pop;@_=sort@_;map{my$a=$n-(my$c=pop);$a>=0&&$r{"$c,$_"}++for X(@_,$a);$a||$r{$c}++}@_;keys%r}
  12.  
  13. sub X { # Основная функция
  14. my$n=pop; # $n=первый параметр (текущий остаток)
  15. @_=sort@_; # Сортируем входной массив
  16. my %r; # Объявляем хеш результатов
  17. map { # перебираем массив
  18. my$a=$n-(my$c=pop); # вытаскиваем очередной элемент массива (в $c)
  19. # и вычисляем текущий остаток минус данный элемент массива
  20. if($a>=0) { # Если он больше или ноль
  21. $r{"$c,$_"}=1 for X(@_,$a) # Кладем в хеш результатов каждый элемент массива,
  22. # который вернет функция перед которым текущий элемент с запятой
  23. }
  24. $r{$c}=1 if!$a # Если разность 0 - то кладем в результаты само число
  25. } @_;
  26. keys%r # возвращаем массив результатов
  27. }
  28.  
  29. # Вызов
  30. @A=(1,3,4,5,3,3,7,2,7,10); # Тестовый массив
  31. $,="n";
  32. print X(@A,10);
  33.  
  34. -- создаём таблицу с данными
  35. CREATE TABLE a (r INTEGER, i INTEGER);
  36.  
  37. -- заполняем
  38. INSERT INTO a VALUES (1,5);
  39. INSERT INTO a VALUES (2,5);
  40. INSERT INTO a VALUES (3,2);
  41. INSERT INTO a VALUES (4,3);
  42.  
  43. WITH t (p, r, s) AS
  44. (SELECT '', 0, 0 FROM dual -- инициализация кортежа для рекурсии
  45. UNION ALL
  46. SELECT
  47. p || a.i || ';' , -- сбор строки для вывода
  48. a.r, -- запоминаем номер строки, чтоб не взять дважды
  49. a.i+s -- накопительная сумма
  50. FROM t, a
  51. WHERE s <= 10 -- выйти из рекурсии, если накопили достаточно
  52. AND a.r > t.r -- ограничение - не использовать уже учтенные строки
  53. )
  54. SELECT DISTINCT p -- выбор уникальных комбинаций
  55. FROM t
  56. WHERE s = 10; --наше конкурсное условие - сумма=10
  57.  
  58. P
  59. 1 5;2;3;
  60. 2 5;5;
  61.  
  62. c[]=[[]]
  63. c(x:l)=c l++[x:r|r<-c l]
  64. g n l=nub$filter((n==).sum)$c$sort l
  65.  
  66. c [] = [[]]
  67. c (x:l) = c l ++ [ x:r | r <- c l ]
  68. g n l = nub $ filter (x -> sum x == n) $ c $ sort l
  69.  
  70. a=>[...Array(1024)].map((x,q)=>a.filter((x,i)=>q&1<<i).sort()).filter((x,i,a)=>x.reduce((x,y)=>x+y,0)==10&!a.find((y,j)=>j<i&""+x==y))
  71.  
  72. def r(a,c=[],z=[]):
  73. a.sort()
  74. for i,v in enumerate(a):z+=[c+[v]]if v+sum(c)==10*0**(c+[v]in z)else r(a[i+1:],c+[v],z)*0
  75. return z
  76.  
  77. res = r( [1,4,5,5,2,3,1,4] )
  78. print( res )
  79.  
  80. def recur( arr, curArr, maxSumm ):
  81. arr.sort()
  82. curSumm = sum( curArr ) # текущая набранная сумма, не забываем, что sum([]) == 0
  83. result = []
  84. for i in range( len( arr ) ):
  85. if arr[i] + curSumm == maxSumm: # если в сумме набрали нужное число, то добавляем к результату
  86. result+=[ curArr + [ arr[i] ] ]
  87. elif arr[i] + curSumm < maxSumm: # если сумма меньше, то добавляем результат рекурсивного вызова
  88. result+= recur( arr[i+1:], curArr + [ arr[i] ], maxSumm )
  89. return result
  90.  
  91. def unique( arr ): # уникальные значения массива
  92. unique = []
  93. [ unique.append(i) for i in arr if i not in unique ]
  94. return unique
  95.  
  96. f=(n,s=0,i=0,r=[],c={})=>{s==10&&(c[r.join(',')]=r);for(;i<n.length;i++)f(n,s+n[i],i+1,[n[i],...r].sort(),c);return c}
  97.  
  98. solve <- function(a) {
  99. # собираем вектор с допустимыми длинами комбинаций
  100. sizes <- c(1:length(a))
  101. # сопоставляем каждой длине комбинации, получаем список списков комбинаций
  102. combinations <- Map(function(size) combn(a, size, FUN = sort, simplify = FALSE), sizes)
  103. # делаем список комбинацией плоским
  104. combinations <- unlist(combinations, recursive = FALSE)
  105. # оставляем только комбинации дающие в сумме 10
  106. combinations <- Filter(function(x) sum(x) == 10, combinations)
  107. # выкидываем дубликаты
  108. combinations <- unique(combinations)
  109. #возвращаем результат
  110. combinations
  111. }
  112.  
  113. s(c(2,3,5,5))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement