1

I'm writing a smart contract (in solidity) that has to handle a function that creates arrays of x elements based on one array with n elements.

For the purposes of this example, I've experimented with arrays of 10 elements (uints) that I am looking for combinations that contain 8 elements. I would expect there to be 45 permutations.

The code (that works for 9 elements), generating 9 unique combinations of 8 elements, is utilising a fairly standard recursive algorithm, below:

function combinations(uint[] memory arr, uint len, uint8 startPosition, uint[8] memory result,address addressFrom) private {

 if (len == 0) {
     entry[addressFrom].push(result); 
     return;
 }       
 for (uint8 i = startPosition; i <= arr.length-len; i++){
     result[result.length - len] = arr[i];
     combinations(arr, len-1, i+1, result, addressFrom);
 }
}      

The function populates a storage mapping entry. I assume I run out of stack space or run into gas limit issues with arrays of 10 or more (always looking for perms of 8 elements).

Is there a more efficient way of doing this or am I running up against computational limits in smart contracts?

0

Your biggest problem is not about recursion but storage.

There are 45 combination of 8 elements out of 10 and you are storing an array for each combination, Each array consumes 9 slots = 8 for elements + 1 for array length. The cost of an slot is 20k gas.

45 * 9 * 20,000 = 8,100,000

The block gas limit on mainnet is around 8M.

Without knowing the details of your problem is hard to make an useful recommendation, a few generic ones:

  • Pack several elements inside an slot.
  • If the array length is constant do not store it.
  • Do not store the arrays, generate them dynamically when needed.
  • Thanks - this is really useful. I also like the idea of generating them dynamically when needed. – Dave R Sep 11 '18 at 17:12
1

The way to avoid unbounded recursion is to invert control and invite a client (possibly with access control) to perform iterations and write permutations. The contract's concerns would include such things as:

  1. Data integrity such as preventing writing a duplicate permutation. This can be accomplished with a hash strategy.
  2. Access control, so only an authorized writer is allowed to supply the information.
  3. Initialization control, so the app doesn't begin servicing requests until the state is fully configured.

Hope it helps.

  • Thanks Rob. I had considered having the client perform the permutation but was concerned that it turns 1 transaction (the client sending 10 elements to the contract which in turn creates the 45 elements) into 45 transactions. Am I missing something? – Dave R Sep 11 '18 at 17:08
  • No, you're not missing anything. Breaking it up into small ops is the desirable thing to do. You don't want processes that increase in cost with scale because that way leads to a broken contract. You want to build it from O(1) processes so the contract works at any scale. You will want to avoid repetition in any case, so look for ways to re-use permutations or possibly externalize that as well. I don't know your use-case so I can't judge if this is really needed. General ideas: blog.b9lab.com/… – Rob Hitchens - B9lab Sep 11 '18 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.