Advertisement
Guest User

Untitled

a guest
Oct 24th, 2016
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.69 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=pop;@_=sort@_;my%r;while($#_+1){my$a=$n-(my$c=pop);if($a>=0){$r{"$c,$_"}=1 for X(@_,$a)}$r{$c}=1 if(!$a)}keys%r}
  12.  
  13. sub X { # Основная функция
  14. my$n=pop; # $n=первый параметр (текущий остаток)
  15. @_=sort@_; # Сортируем входной массив
  16. my %r; # Объявляем хеш результатов
  17. while($#_+1) { # пока есть еще параметры
  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. a=>Array(1024).fill``.map((x,q)=>a.filter((x,i)=>q&1<<i).sort()).filter(x=>x.reduce((x,y)=>x+y,0)==10).filter((x,i,a)=>!a.find((y,j)=>j<i&""+x==y))
  35.  
  36. -- создаём таблицу с данными
  37. CREATE TABLE a (r INTEGER, i INTEGER);
  38.  
  39. -- заполняем
  40. INSERT INTO a VALUES (1,5);
  41. INSERT INTO a VALUES (2,5);
  42. INSERT INTO a VALUES (3,2);
  43. INSERT INTO a VALUES (4,3);
  44.  
  45. WITH t (p, r, s) AS
  46. (SELECT '', 0, 0 FROM dual -- инициализация кортежа для рекурсии
  47. UNION ALL
  48. SELECT
  49. p || a.i || ';' , -- сбор строки для вывода
  50. a.r, -- запоминаем номер строки, чтоб не взять дважды
  51. a.i+s -- накопительная сумма
  52. FROM t, a
  53. WHERE s <= 10 -- выйти из рекурсии, если накопили достаточно
  54. AND a.r > t.r -- ограничение - не использовать уже учтенные строки
  55. )
  56. SELECT DISTINCT p -- выбор уникальных комбинаций
  57. FROM t
  58. WHERE s = 10; --наше конкурсное условие - сумма=10
  59.  
  60. P
  61. 1 5;2;3;
  62. 2 5;5;
  63.  
  64. def r(a,c=[],z=[]):
  65. a.sort()
  66. 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
  67. return z
  68.  
  69. res = r( [1,4,5,5,2,3,1,4] )
  70. print( res )
  71.  
  72. def recur( arr, curArr, maxSumm ):
  73. arr.sort()
  74. curSumm = sum( curArr ) # текущая набранная сумма, не забываем, что sum([]) == 0
  75. result = []
  76. for i in range( len( arr ) ):
  77. if arr[i] + curSumm == maxSumm: # если в сумме набрали нужное число, то добавляем к результату
  78. result+=[ curArr + [ arr[i] ] ]
  79. elif arr[i] + curSumm < maxSumm: # если сумма меньше, то добавляем результат рекурсивного вызова
  80. result+= recur( arr[i+1:], curArr + [ arr[i] ], maxSumm )
  81. return result
  82.  
  83. def unique( arr ): # уникальные значения массива
  84. unique = []
  85. [ unique.append(i) for i in arr if i not in unique ]
  86. return unique
  87.  
  88. 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}
  89.  
  90. c[]=[[]]
  91. c(x:l)=c l++[x:r|r<-c l]
  92. g n l=nub$filter((n==).sum)$c$sort l
  93.  
  94. c [] = [[]]
  95. c (x:l) = c l ++ [ x:r | r <- c l ]
  96. g n l = nub $ filter (x -> sum x == n) $ c $ sort l
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement