spot7.org logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML Categories

How to iterate through all cases when partitioning objects


I managed to find a solution through a combination of recursion and loop.

Here's the pseudo code (I have no idea how to write pseudo code...I'm denoting a list by [a; b; c ...]:

// Returns a list of integers in range
[0, k].
function num_list k =
...


// Recursively generate all the possible
partitions with [total] objects
// and [groups] partitions. Returns a list of list
of integers.
function generate (int groups, int total) = {
    if (groups == 1) then {
        return [[total]];
    } else {
        int list nums = num_list total;
        // looping through all values for one of
the partitions.
        int list list list container1;
        foreach (i in nums) {
            // recursive step - generate all
combinations without the first 
            // partition
            int list list subset = generate
(groups - 1) (total - i);
            // append the first partition onto
each element of this list
            int list list container2 = [];
            foreach (l in subset) {
                container2.add(l.prepend i);
            }
            container1.add container2;
        }
        // Flatten just takes a list of lists, and
extract everything in each
        // list and mesh everything together.
        return container1.flatten();
}

Here's the code in python:

# Recursively generate all the possible
partitions with [total] objects
# and [groups] partitions. Returns a list of list
of integers.
def generate (groups, total):
    if (groups == 1):
        return [[total]];
    else:
        nums = range(total + 1);
        # looping through all values for one of
the partitions.
        container1 = [];
        for i in nums:
            # recursive step - generate all
combinations without the first 
            # partition
            subset = generate (groups - 1, total -
i);
            # append the first partition onto each
element of this list
            container2 = [];
            for l in subset:
                container2 += [([i] + l)];
            container1 += [container2];
        # Flatten just takes a list of lists, and
extract everything in each
        # list and mesh everything together.
        return [item for sublist in container1 for
item in sublist];

And here's the code in...functional programming language ocaml:

(* Returns a list of integers in range
[0, k]. *)
let num_list n : int list =
  let rec helper num =
    if num = 0 then
      [0]
    else
      num :: (helper (num - 1)) in
  List.rev (helper n)

(**
 * Recursively generate all the combinations when
dividing total number of
 * objects among groups.
 *)
let rec generate groups total : int list list =
  (* generate all the possible *)
  match groups, total with
  | 1, t -> [[t]]
  | g, t -> 
    let nums = num_list t in
    (* looping through all values for the head
group *)
    let helper e : int list list =
      let subset = generate (g - 1) (t - e) in
      (* appending in front of every single result
from generate *)
      List.map (fun l -> e :: l) subset in
    List.flatten (List.map helper nums)

Categories : Algorithm

Related to : How to iterate through all cases when partitioning objects
Clojure: 'folding' a sequence (partitioning, as it turned out)
(->> '(1 2 3 4 5 6 7 8 9) (partition 3) (map vec)) Take the original list and then partition it by 3 and finally map each partition to a vector. I think using the ->> macro makes it read nicer.

Categories : Clojure
Partitioning a weighted tree to equally weighted subtrees
Assume you can't modify the tree other than to remove edges to create subtrees. First understand that you cannot guarantee that by simply removing edges that you will have subtrees within an arbitrary bound. You can create tree that when you split them there is no way to create subtrees within a target bound. For example: a(b(c,d,e,f),g) You cannot split that into two balanced sections. The be

Categories : Algorithm
use cases of googleMaps distanceMatrix api?
Consider the M x N case: You have a delivery merchandise (pizza joint) with M not-currently-occupied vehicles in a predefined area, and N different target locations to serve at a given slice of time. In order to find the optimal route to N locations for your vehicles, you could run a distance matrix query and match the closest driver to the appropriate itinerary. Second example: As a regional b

Categories : Google Maps
Android - Detecting various cases of app installation
The purpose of putting in the Google Play Store is for people to find and use your app. Once they have the link to it, anyone can reach it and try to install it. However if all you want is a way to tie back to what was the driver of that install/launch then you may want to look at: Google Play Campaign Attribution If you want to limit your requirements on Google APIs or using a store other than

Categories : Android
How to set activity no history parameter only in some cases?
Call finish() after doing startActivity() to remove previous activity from the stack. Like so: if (isCorrespondingKiboAppInstalled) { Intent launchIntent = getPackageManager().getLaunchIntentForPackage(kiboAppPackageName); startActivity(launchIntent); finish(); }

Categories : Java
Recently Add
Maximum weighted pairing algorithm for complete graph
How many iterations until the Hilbert Curve passes through a point?
Data structure to pre-process given set of N points and given a query parallel strip output all points lie within the strip
Recurrance relation: T (n/16) + n log n
Proving optimality for a new algorithm that finds spanning tree with contradiction
Starting values for elo
Proving optimality for a new algorithm that finds minimum spanning tree
why this assembly piece of code do jmp forever
Find out if segment is fully inside of polygon
Algorithm for coloring a hexagon tile map with minimum distance (3) for reoccurring colors
Sort pairs to be more consecutive
To find three unique numbers whose number of occurrence is even
Dealing with duplication between unit and integration tests
reflection and symmetry in back tracking queens
Big O analysis for method with multiple parameters
Divide Huge Array of Numbers in Buckets
Algorithm to find adjacent cells in a matrix
Why this code gives WA for Petersen Graph(codechef)?
Complexity of this prime number search algorithm
How to detect if a file has changed?
Given string x,y and z. Determine if z is a shuffle
Basic decryption for simple encryption algorithm
An efficient way to assign user_ids to huge dataset under certain conditions
What's a more efficient implementation of this puzzle?
Generating prime numbers in poly-time
What if I do not use G transpose in calculating Strongly Connected Components?
Dividing an array into optimum no of equal sum sublists
Counting derangements
How to iterate through all cases when partitioning objects
Algorithm: How to find closest element, having coordinates and dimension
© Copyright 2017 spot7.org Publishing Limited. All rights reserved.