Intent

For the final project in my Python Data Structures course, we were given a complex problem with an open ended solution. The Partition Constraint Problem asked us to create partitions using an original collection of integers and two constraint parameters. Each partition must satisfy a minimum sum (k), a minimum diversity (l non-zero indices), and jointly reconstruct the original collection exactly when summed index-wise. Then among all valid solutions, the goal was to maximize the number of partitions using two different algorithmic approaches. These approaches are:

• Greedy: A greedy “largest-first” partition builder that acts directly on the original list of values.
• Alternative: An approach that we came up with on our own. For me, I designed a dynamic tree-based approach that uses a binary splitting tree of linked-list nodes and then chooses partitions via a memorized decision procedure.

Example Partition:

Original Collection: [10, 5, 8]
Constraints: k = 10, l = 2

Valid Solution:

Partition 1: [7, 3, 0] → Sum = 10 ≥ k ✓   Non-empty indices: 2 ≥ 1 ✓

Partition 2: [3, 2, 8] → Sum = 13 ≥ k ✓   Non-empty indices: 3 ≥ 1 ✓

Verification:

• Index 0: 7 + 3 = 10 ✓
• Index 1: 3 + 2 = 5 ✓
• Index 2: 0 + 8 = 8 ✓
• All original values reconstructed correctly!

Algorithm 1

Download Python Code

Algorithm 1 directly manipulates the “remaining” copy of the original values and repeatedly constructs partitions greedily.

At each step:
1. It attempts to build a single valid partition using the procedure build_one_partition.

2. This procedure repeatedly takes one unit from whichever index currently has the largest remaining value and places it into the current partition.

3. It keeps track of:

• The total sum of the partition so far.
• The diversity, defined as the number of distinct indices where the partition is non-zero.

The process for a given partition stops as soon as both the sum constraint (≥ k) and the diversity constraint (≥ l) are satisfied. That partition is then committed, and the “remaining” array is updated accordingly. This is repeated until no more valid partitions can be formed. If there is leftover mass (i.e., the sum of remaining values is greater than zero) after the last successful partition, the leftover is added into the first partition to preserve exact reconstruction.

Key Helper Functions

The implementation in algorithm1.py provides several helper functions:

• partition_sum(partition): Returns the sum of the partition.
• partition_diversity(partition): Counts how many indices in the partition are strictly positive.
• check_reconstruction(partitions, original): Verifies that summing all partitions index-wise reconstructs the original list.
• build_one_partition(remaining, k, l): Attempts to construct a single valid partition, using a local copy (temp_remaining) so the algorithm can abort cleanly if it fails.

The main driver function:

greedy_partition_algorithm(values, k, l): Repeatedly calls build_one_partition until no more valid partitions can be created, folds leftover mass into an existing partition, if possible, runs the reconstruction check, and returns success status plus the list of partitions.

The script also includes input validation in the main block, which:

• Prompts for a space-separated list of integers.
• Prompts for k and l, rejecting invalid (non-integer) inputs.
• Prints either a failure message or the list of partitions, along with a reconstruction check and average runtime using the timeit module.

Algorithm 2

Download Python Code

Algorithm 2 uses a two-stage process: a binary splitting tree built from linked lists, followed by a dynamic programming decision over the tree.

The steps are:
1. Convert the original list of integers into a linked list (ListNode). This is then turned into the root of a binary tree (TreeNode), where each node stores a linked list.

2. Using a splitting rule, each node’s list is recursively split into left and right child lists until no element greater than 1 remains (i.e., all values are 0 or 1).

3. Once the tree is built, a dynamic programming function compute_best_partitions decided, for every TreeNode, whether it is better to:

• Treat that node’s list as a single partition (if it satisfies k and l), or
• Take the best combination of partitions from its children.

4. A separate function collect_partitions then walks the tree according to these choices and produces the final list of partitions.

Data Structures

The algorithm uses three core data structures:

• ListNode: A singly linked list node storing a single integer and a pointer to the next node.
• TreeNode: A binary tree node storing:
  • list_head: the head of a linked list (the current “collection” at this node).
  • left, right: pointers to child TreeNodes.
• A memorization dictionary “memo” that maps TreeNode objects to a result: (best_count, choice), where choice is either "self" or "children".

Splitting Procedure and Tree Construction

The helper functions are:

• build_linked_list(values): Converts a Python list into a linked list.
• linked_list_to_list(head): Converts a linked list back into a Python list.
• can_split_list(list_head): Returns True if any element in the list is greater than 1, meaning further splitting is possible.
• split_list(list_head): For each element x in the list:
  • If x > 1
  • If x is even, split into (x/2, x/2).
  • If x is odd, split into (floor(x/2), floor(x/2) + 1).
  • If x ≤ 1
  • Left child gets x; right child gets 0 (so that reconstruction remains possible but splitting effectively stops).
• _build_children(node): recursively splits a node into its left and right children as long as its list can be split, thereby creating a binary tree whose leaves are lists of 0s and 1s (and possible leftover values).

Dynamic Construction Of Partitions Using The Tree

Once the splitting tree is built, the goal is to choose a set of TreeNodes to treat as partitions such that:

• Each chosen node’s list satisfies sum ≥ k and diversity ≥ l.
• The choice is consistent with the tree structure: if we treat a node as "self", we do not also take its descendants as separate partitions.
• • The total number of chosen partitions is maximized.

Key Functions

• list_sum_and_diversity(list_head): Computes total sum and diversity (count of positive entries) for a list.
• compute_best_partitions(node, k, l, memo): At a given TreeNode, compute:
  • A “self” option: treat this node’s list as one partition if it satisfies k and l.
  • A “children” option: recursively compute best partitions for left and right children and sum their counts, if both are feasible. Then:
  • Choose whichever option yields the larger number of partitions.
  • Store the result (best_count, choice) in memo and return it.
• collect_partitions(node, memo, partitions): Uses the memorized choices to actually collect the lists representing partitions.
• If choice == "self", the node’s linked list is converted back to a Python list and appended as a partition.
• If choice == "children", the function recurses on left and right child nodes.

Driver Function

tree_based_dp_algorithm(values, k, l):

• 1. Performs quick feasibility checks on the total sum and global diversity (like Algorithm 1).
• 2. Build the splitting tree from the original list.
• 3. Runs compute_best_partitions on the tree’s root.
• 4. Calls collect_partitions to generate the list of partitions based on the DP choices.
• 5. Verifies reconstruction using check_reconstruction_from_partitions.
• 6. Returns success status and the resulting partitions.

My Conclusion

This project implemented and analyzed two distinct algorithms for the Partition Constraint Problem: a straightforward greedy largest-first method (Algorithm 1) and a more structured tree-based dynamic programming approach (Algorithm 2). Both algorithms successfully enforce the sum constraint, diversity constraint, and reconstruction property, and both handle impossible cases correctly.

In practice, the greedy algorithm often produced as many or more partitions than the tree-based algorithm, despite lacking formal optimality guarantees and being conceptually simpler. The tree-based DP, while theoretically appealing within its splitting structure, is limited by the expressiveness of that structure and carries additional overhead in both time and implementation complexity.

Overall, the project demonstrates how different algorithmic perspectives—local greedy heuristics versus structured dynamic programming, can be applied to the same combinatorial optimization problem, and how practical considerations and structural constraints can shape which approach performs better under real input conditions.