arrays,ruby,permutation , a repeated permutation with limitations

## Question:

Tag: arrays,ruby,permutation

I am trying to generate all possible combinations of certain values in an array of 15 which add up to 50.

``````\$a = [3, 4, 1, 2, 5]
print \$a.repeated_permutation(15).to_a
``````

In this case,

``````[2,2,2,2,4,4,4,4,4,4,4,4,4,3,3]
[2,2,2,4,2,4,4,4,4,4,4,4,4,3,3]
[2,2,4,2,2,4,4,4,4,4,4,4,4,3,3]
``````

After some investigation I realize the code to do this is a bit over my head, but I will leave the question up if it might help someone else.

For some reference as to what I am working on, Project Euler, problem 114. It's pretty difficult, and so I am attempting to solve only a single case where my 50-space-long grid is filled only with 3-unit-long blocks. The blocks must be separated by at least one blank, so I am counting the blocks as 4. This (with some tweaking, which I have left out as this is confusing enough already) allows for twelve blocks plus three single blanks, or a maximum of fifteen elements.

Approach

I think recursion is the way to go here, where your recursive method looks like this:

``````def recurse(n,t)
``````

where

• `n` is the number of elements required; and
• `t` is the required total.

If we let `@arr` be the array of integers you are given, `recurse(n,t)` returns an array of all permutations of `n` elements from `@arr` that sum to `t`.

Assumption

I have assumed that the elements of `@arr` are non-negative integers, sorted by size, but the method can be easily modified if it includes negative integers (though performance will suffer). Without loss of generality, we can assume the elements of `@arr` are unique, sorted by increasing magnitude.

Code

``````def recurse(n,t)
if n == 1
@arr.include?(t) ? [[t]] : nil
else
@arr.each_with_object([]) do |i,a|
break if i > t # as elements of @arr are non-decreasing
if (ret = recurse(n-1,t-i))
ret.each { |b| a << [i,*b] }
end
end
end
end
``````

Examples

``````@arr = [3, 4, 1, 2, 5].sort
#=> [1, 2, 3, 4, 5]

recurse(1,4)
#=> [[4]]
recurse(2,6)
#=> [[1, 5], [2, 4], [3, 3], [4, 2], [5, 1]]
recurse(3,10)
#=> [[1, 4, 5], [1, 5, 4], [2, 3, 5], [2, 4, 4], [2, 5, 3],
#    [3, 2, 5], [3, 3, 4], [3, 4, 3], [3, 5, 2], [4, 1, 5],
#    [4, 2, 4], [4, 3, 3], [4, 4, 2], [4, 5, 1], [5, 1, 4],
#    [5, 2, 3], [5, 3, 2], [5, 4, 1]]
recurse(3,50)
#=> []
``````

Improvement

We can do better, however, by first computing all combinations, and then computing the permutations of each of those combinations.

``````def combo_recurse(n,t,last=0)
ndx = @arr.index { |i| i >= last }
return nil if ndx.nil?
arr_above = @arr[ndx..-1]
if n == 1
arr_above.include?(t) ? [[t]] : nil
else
arr_above.each_with_object([]) do |i,a|
break if i > t # as elements of @arr are non-decreasing
if (ret = combo_recurse(n-1,t-i,i))
ret.each { |b| a << [i,*b] }
end
end
end
end

combo_recurse(1,4)
#=> [[4]]
combo_recurse(2,6)
#=> [[1, 5], [2, 4], [3, 3]]
combo_recurse(3,10)
#=> [[1, 4, 5], [2, 3, 5], [2, 4, 4], [3, 3, 4]]
combo_recurse(3,50)
#=> []
combo_recurse(15,50).size
#=> 132
combo_recurse(15,50).first(5)
#=> [[1, 1, 1, 1, 1, 1, 4, 5, 5, 5, 5, 5, 5, 5, 5],
#    [1, 1, 1, 1, 1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5],
#    [1, 1, 1, 1, 1, 2, 4, 4, 5, 5, 5, 5, 5, 5, 5],
#    [1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5],
#    [1, 1, 1, 1, 1, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5]]
``````

We can then compute the permutations from the combinations:

``````combo_recurse(2,6).flat_map { |a| a.permutation(a.size).to_a }.uniq
#=> [[1, 5], [5, 1], [2, 4], [4, 2], [3, 3]]
combo_recurse(3,10).flat_map { |a| a.permutation(a.size).to_a }.uniq
#=> [[1, 4, 5], [1, 5, 4], [4, 1, 5], [4, 5, 1], [5, 1, 4],
#    [5, 4, 1], [2, 3, 5], [2, 5, 3], [3, 2, 5], [3, 5, 2],
#    [5, 2, 3], [5, 3, 2], [2, 4, 4], [4, 2, 4], [4, 4, 2],
#    [3, 3, 4], [3, 4, 3], [4, 3, 3]]
``````

We can approximate the number of permutations for `(15,50)` (it will be somewhat high because `uniq` is not applied):

``````def factorial(n)
(1..n).reduce :*
end

Math.log10 combo_recurse(15,50).reduce(1) { |t,a| t*factorial(a.size) }
#=> 1599.3779486682888
``````

That is, the result has about 1,600 digits. What platform will you be running this on?

# Related:

## Substring of a file

javascript,arrays,substring
I have a file that is structure like this : var file = "a|b|c|d, a|b|c|d, a|b|c|d, a|b|c|d, a|b|c|d"; Now I would extract all letters "c" and "d" of this file and put those letter in array, structure like this: var array = [ [a,b,1], [a,b,2], [a,b,3], [a,b,4], [a,b,5] ]; How...

## C++ & Qt: Random string from an array area

c++,arrays,string,qt,random
In my small Qt application, I want to pick a random string out of an array after I clicked on a button. I've read many threads but nothing works for me. So in my slot there's an array with several strings in it. I also implemented <string>, <time.h> and srand....

## Zipping two arrays together with index in Scala?

arrays,scala,zip
I have two arrays populated with integers. They are the same size (val array1 and val array2). I want to fuse them together into tuples with their index as the third element. For example if we have val array1 = Array(5,2,6,2) and val array2 = Array(9,8,3,4) then I want to...

## Javascript function to validate contents of an array

javascript,arrays
Here's what is asked: validItems(items) – this function receives a string array of items which are to be for a customer. The function returns an empty string indicating all item codes in the array are valid; otherwise the function returns the first invalid item code in the array. All item...

## For loop with flexible stop variable

ruby
I need to write a loop for x in (1..y) where the y variable can be changed somehow. How can I do that? For example: for x in (1..y/x) But it does not work. ...

## Translating a character array into a integer string in C++

c++,arrays,string
I was trying to achieve translating a character array into a integer string and corresponding character to their alphabetical order. For instance: A(a) = 0 , Z(z) = 25. string key_char = argv[1]; string key_num; for (int i = 0; i < key_char.length(); i++){ if (isalpha(key_char[i])){ if (islower(key_char[i])){ key_num[i] =...

## Stack level too deep because recursion

I have a model named Tweet. The columns of the Tweet model are: -id -content -user_id -picture -group -original_tweet_id Every tweet can have one or multiple retweets. The relation happens with the help of original_tweet_id. All the tweets have original_tweet_id nil , whilst the retweets contain the id of the...

## array and function php

php,arrays
I'm just a beginner in PHP coding. I've been reading through a tutorial, but having some trouble with basic PHP concepts. If you could help me, I'd be much obliged. I'm having trouble understanding why the following code doesn't work. <?php function sum(\$x, \$y) { \$z = \$x + \$y;...

## Keep leading zeroes when converting string to integer

ruby
For no particular reason, I am trying to add a #reverse method to the Integer class: class Integer def reverse self.to_s.reverse.to_i end end puts 1337.reverse # => 7331 puts 1000.reverse # => 1 This works fine except for numbers ending in a 0, as shown when 1000.reverse returns 1 rather...

## How to pivot array into another array in Ruby

arrays,ruby,csv
I have a multidimensional array like this one : myArray = [["Alaska","Rain","3"],["Alaska","Snow","4"],["Alabama","Snow","2"],["Alabama","Hail","1"]] I would like to end up with CSV output like this. State,Snow,Rain,Hail Alaska,4,3,nil Alabama,2,nil,1 I know that to get this outputted to CSV the way I want it I have to have output array like this: outputArray =[["State","Snow","Rain","Hail"],["Alaska",4,3,nil],["Alabama",2,nil,1]]...

ruby-on-rails,ruby,rest,activerecord,one-to-many
I'm creating a rails application that is a backend for a mobile application. The backend is implemented with a RESTful web API. Currently I am trying to add gamification to the platform through the use of badges that can be earned by the user. Right now the badges are tied...

## Comparing arrays with numbers in vb.net

arrays,vb.net
I need a way to compare two arrays in vb.net and save result in third array: Dim KonRes(3) As Integer Dim UserRes(3) As Integer Dim YelRed(3) As Integer KonRes(0) = 1 KonRes(1) = 2 KonRes(2) = 3 KonRes(3) = 4 UserRes(0) = 4 UserRes(1) = 3 UserRes(2) = 2 UserRes(3)...

## Ruby- get a xml node value

ruby,xml
can someone help me in extracting the node value for the element "Name". Type 1: I am able to extract the "name" value for the below xml by using the below code <Element> <Details> <ID>20367</ID> <Name>Ram</Name> <Name>Sam</Name> </Details> </Element> doc = Nokogiri::XML(response.body) values = doc.xpath('//Name').map{ |node| node.text}.join ',' puts values...

## How to pass array in rails 4 strong parameters

ruby-on-rails,arrays
I have to pass a array of food_item_ids in my order_controller. Every order will have many food_items. How can I pass these food_items_id as an array in strong parameters. orders_controller.rb def create @order = Order.new(order_params) if @order.save render :json, @order, status:201, location: [:api, @order] else render :json, { errors: @order.errors...

## Allowing some enabled and disabled option on collection_select

ruby-on-rails,ruby
I am trying to populate a dropdown box on a view that has all the states. This works just fine: <%= f.collection_select :state_id, @states, :id, :name %> Now, I need to make the following: Some states are going to be disabled for choosing, but they still have to appear on...

## pointer to pointer dynamic array in C++

c++,arrays,pointers
I've been having bad luck with dynamic pointers when I want to close it. why the application wrote to memory after end of heap buffer? how can I close my array? int main() { . . int **W; W = new int* [n]; for (int i=1; i <= n; i++)...

## What is Rack::Utils.multipart_part_limit within Rails and what function does it perform?

ruby-on-rails,ruby,rack,multipart
Rack::Utils.multipart_part_limit is set to 128 by default. What purpose does the value have and what effect does it have within the Rails system?...

## Ruby: How to copy the multidimensional array in new array?

ruby-on-rails,arrays,ruby,multidimensional-array
seating_arrangement [ [:first, :second, :none], [:first, :none, :second], [:second, :second, :first], ] I need to copy this array into new array. I tried to do it by following code: class Simulator @@current_state def initialize(seating_arrangement) @@current_state = seating_arrangement.dup end But whenever I am making any changes to seating_arrangement current_state changes automatically....

## How do I print more than one value per key in Tcl?

arrays,tcl
array set array_in_twos { set1 table set2 chair set1 chair } foreach combo [array names array_in_twos] { puts "\$combo is \$array_in_twos(\$combo)," } outputs: set1 is chair, set2 is chair, It seems the second 'set 1' replaces the first 'set 1'. how do i print all? set1 is table, set2 is...

## Create array from another with specific indices

javascript,arrays
I have two arrays, one of data and one of indices: var data = [ 'h', 'e', 'l', 'l', 'o', ' ' ]; var indices = [ 4, 0, 5, 0, 1, 2, 2 ]; I would like to create a third array, using cells of data in order indicated...

## Same enum values for multiple columns

ruby-on-rails,ruby,enums
I need to do something like this: class PlanetEdge < ActiveRecord::Base enum :first_planet [ :earth, :mars, :jupiter] enum :second_planet [ :earth, :mars, :jupiter] end Where my table is a table of edges but each vertex is an integer. However, it seems the abvove is not possible in rails. What might...

## On rendering from controller, current_page method does not seem to work

ruby-on-rails,ruby,ruby-on-rails-4,model-view-controller
I have a navigation bar included in application.html.erb. Because for some pages, such as the signup page, I need to place additional code inside the navigation bar, I have excluded those pages for showing the navigation bar through application.html.erb and instead included it in their respective view pages. See code...

## Rails Association Guidance [on hold]

ruby-on-rails,ruby,ruby-on-rails-4,ruby-on-rails-3.2
I am new to rails 4. I have gone through lots of tutorials and trying to solve below scenario. But still no success. Can anybody point me in the right direction. How to handle associations for below scenario. Scenario: 1. Patient can have many surgeries. 2. Surgery has two types...

## Loop until i get correct user

ruby,redis
I have users stored in Redis and want to be able to call only certain subsets from a set, if i don't get the correct user back i want to put it back in the set and then try again until i get one of the desired users @redis =...

## most efficient way to create javascript array out of various php arrays

javascript,php,jquery,arrays
I have a form that a user can submit multiple times, adding different information each time. These form inputs are translated into php \$_SESSION arrays, so each time the user hits the submit button, the array grows. This is working fine. I need to bring these over into javascript but...

## Heroku RAM not increasing with upgraded dynos

ruby-on-rails,ruby,ruby-on-rails-3,memory,heroku
I have a massive function i have been calling manually through the heroku rails console. I have been receiving the error rapid fire in my logs: 2015-06-22T14:56:42.940517+00:00 heroku[run.9877]: Process running mem=575M(112.4%) 2015-06-22T14:56:42.940517+00:00 heroku[run.9877]: Error R14 (Memory quota exceeded) A 1X dyno is suppose to have 512 MB of RAM. I...

## accessing range of values in arduino array

arrays,arduino
I have data packet coming in like this in Arduino. Data: 12345678901234 I can access the 5th value using the code below. id = sx1272.packet_received.data[4]; My question is how do I access a rang of values? I tried this, but the colon throws an error. char[2] id; if( sx1272.packet_received.length >...

## Rails shared controller actions

ruby-on-rails,ruby,ruby-on-rails-4
I am having trouble building a controller concern. I would like the concern to extend the classes available actions. Given I have the controller 'SamplesController' class SamplesController < ApplicationController include Searchable perform_search_on(Sample, handle: [ClothingType, Company, Collection, Color]) end I include the module 'Searchable' module Searchable extend ActiveSupport::Concern module ClassMethods def...

## Blank screen on GridView

android,arrays,gridview
I'm trying to create a GridView with an array of strings. These are XML, and MainActivity and Adapter, but what I get is a blank screen. I'm change the background, but the result is the same, but clicking on a point on the screen appears to me the toast stating...

## do calculation inside JSONArray in Java

java,arrays,json
I have a simple issue but cannot solve it as I am not very good at algorithm! I have an JSONArray in this form: [{"values":[{"time":1434976493,"value":"50"}, {"time":1434976494,"value":"100"}],"counter":"counter1"}, {"values":[{"time":1434976493,"value":"200"}, {"time":1434976494,"value":"300"}],"counter":"counter2"}, {"values":[{"time":1434976493,"value":"400"}, {"time":1434976494,"value":"600"}],"counter":"total"}] What I want to do is to get the integer value for counter 1 and counter 2 and then divide...

I'm trying to allocate an array 64 bytes in size and then loop over the array indexes to put a read a byte each from the inputfile. but when I don't malloc() the array indexes, the loop stays in index0 (so each time it loops it replaces the content in...

## Javascript sort array of objects in reverse chronological order

javascript,arrays,sorting
I have an array of objects which holds a list of jobs and I would like to sort them in reverse chronological order as they would appear on a resume for example. I came up with the below solution which 'seems' to work but I was wondering if there is...

## Ruby access words in string

ruby
I don't understand the best method to access a certain word by it's number in a string. I tried using [] to access a word but instead it returns letter. puts s # => I went for a walk puts s[3] # => w ...

## Notice: Array to string conversion in “path of php file” on line 64

php,mysql,arrays,oracle
PHP CODE -: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Untitled Document</title> </head> <body> <?php \$rows =0; \$fp = fopen("leave1.csv","r"); if(\$fp){ while(!feof(\$fp)){ \$content = fgets(\$fp); if(\$content) \$rows++; } } fclose(\$fp); //echo \$rows; \$_SESSION['rows'] = \$rows; ?>...

## Array in Foreach (CodeIgniter)

php,arrays,codeigniter,foreach
I want to use array in foreach loop but failed, here is my code: foreach(\$this->db->get_where('mytable', array('result' => '1 or 2', 'id' => 'foo'))->result_array() I think 'result' => '1 or 2'piece has a problem but I couldn't find out how can I use array in this kind of foreach. I want...

## How to innerHTML a function with array as parameter?

javascript,arrays,loops,foreach,innerhtml
I am learning about looping thorugh arrays - I want to pass the result of an if else statement in the forEach function (inside another function with array as parameter) to HTML using innerHTML (does not have to be innerHTML if you know better methods I do not mind). It...

## Rails basic auth not working properly

ruby-on-rails,ruby,authentication
I am building a small API that uses basic authentication. What I have done, is that a user can generate a username and password, that could be used to authenticate to the API. However I have discovered that it is not working 100% as intended. It appears that a request...

## Having two arrays in variable php

php,mysql,arrays,variables,multidimensional-array
i've this code, i'm trying to explode my date e.g "04 June 2015" to have the day and the month in other 2 variables, but i have all in a method, with an array, is it possible, my code doesn't work, it writes "Array[0]" why? while (\$i < \$number) {...

## Ruby boolean logic: some amount of variables are true

ruby
Let say I have 3 variables: a, b, c. How can I check that just zero or one of them is true?...

## Make instance variable accessible through hash in Ruby

ruby-on-rails,ruby,ruby-on-rails-4,activerecord
In Rails, ActiveRecord objects, attributes are accessible via method as well as through Hash. Example: user = User.first # Assuming User to be inheriting from ActiveRecord::Base user.name # Accessing attribute 'name' via method user[:name] # Attribute 'name' is accessible via hash as well How to make instance variables accessible through...

## SCALA: change the separator in Array

arrays,string,scala,delimiter
I have an Array like this. scala> var x=Array("a","x,y","b") x: Array[String] = Array(a, x,y, b) How do I change the separator comma in array to a :. And finally convert it to string like this. String = "a:x,y:b" My aim is to change the comma(separators only) to other separator(say,:), so...

## Heroku rake db:migrate failing - uninitialized constant

ruby-on-rails,ruby,heroku
My app is working fine locally and my push to Heroku was successful. But, when I run heroku run rake db:migrate, I get the following error: NameError: uninitialized constant AddWeightToExercises Here is the failed migration: class AddWeightToExercise < ActiveRecord::Migration def change add_column :exercises, :weight, :float end end edit: Thanks for...

## Perl: Using Text::CSV to print AoH

arrays,perl,csv
I have an array of hashes (AoH) which looks like this: \$VAR1 = [ { 'Unit' => 'M', 'Size' => '321', 'User' => 'test' } { 'Unit' => 'M' 'Size' => '0.24' 'User' => 'test1' } ... ]; How do I write my AoH to a CSV file with separators,...

## Segmentation Fault if I don't say int i=0

c,arrays,segmentation-fault,initialization,int
void removeVowels(char* array){ int i,j,v; i=0; char vowel[]={'a','e','i','o','u'}; while(array[i]!='\0') { for(v=0;v<5;v++) { if (array[i]==vowel[v]) { j=i; while(array[j]!='\0') { array[j]=array[j+1]; j++; } i--; break; } } i++; } } in function removeVowels() if I don't include i=0; and just say int i; why does it give segmentation fault? Isn't it automatically...

## Merge and sum values and put them in an array

javascript,arrays,angularjs,foreach
I'm retrieving values from an external source and apply a foreach loop to the results, with the code below. angular.forEach(data, function(value, key) { if (value.start_date > firstdayOfWeek && value.start_date < lastdayOfWeek) { console.log(value.firstname + ' - ' + value.distance); } else { //do nothing } }); The result is console...

## Get the actual value of a boolean attribute

ruby,page-object-gem,rspec3,rspec-expectations
I have the span: <span disabled="disabled">Edit Member</span> When I try to get the value of the disabled attribute: page.in_iframe(:id => 'MembersAreaFrame') do |frame| expect(page.span_element(:xpath => "//span[text()='Edit Member']", :frame => frame).attribute('disabled')).to eq("disabled") end I get: expected: "disabled" got: "true" How do I get the value of specified attribute instead of a...

## jQuery - Value in Function

jquery,arrays,function
My array: array.name = "Thiago"; array.date = "01/01/1990"; I want a function like this: function myFunc( array, fieldToCompare, valueToCompare ) { if( array.fieldToCompare == "Thiago" ) alert(true); } myFunc( myArray, name, "Thiago" ); is it possible?...

## Get elements containing text from array

javascript,jquery,html,arrays,contains
I want to search all the elements containing any string in the array. For example I have following list of items <ul> <li>cricket bat</li> <li>tennis ball</li> <li>golf ball</li> <li>hockey stick</li> </ul> and this array var arr = ['bat', 'ball']; It should select all the elements having text bat and ball....