to find unequal partitions of an integer in php

Question

I have total partitions of an integer and I want only those partitions which have all the values unequal.

For ex.

-Partitions of 3 are {1,1,1,1},{2,2},{3,1},{1,1,2} and {4}.

So, the required unequal partitions are {3,1} and {4} because they contain no equal elements.I can filter the partitions to get the desired result, but I want some efficient way to find all the partitions, which have no equal terms in them, without finding all the partitions. I have searched the net and StackOverflow but nothing states exactly the problem that I am facing. Every idea is appreciated. Thanks.

what have you tried? please post sample code to improve your post — OLIVER.KOO, Jul 08 '17 at 07:28
I think your example shows the partitioning of 4 and not of 3. — tim, Jul 08 '17 at 07:30
Your title says "in php", but your tags say "python". Which do you want? — Mark Dickinson, Jul 08 '17 at 12:11

score 1 · Answer 1 · answered Jul 08 '17 at 07:30

1

I would just use sets for this:

partitions = [[1,1,1,1], [2,2], [3,1], [1,1,2], [4]]

unique_partions = [p for p in partitions if len(p) == len(set(p))]

answered Jul 08 '17 at 07:30

Turn

6,656
32
41

1

He wants to make it fast by directly filtering the ones with equal values in it before finishing the whole patritioning. – tim Jul 08 '17 at 07:34
Sorry, I don't understand what you mean. Can you elaborate? – Turn Jul 10 '17 at 18:55

tim · Answer 2 · 2017-07-08T07:46:27.917

Ok, so you want to have speed, right?

I guess the speed comes from the best possible partitioning algorithm with memorization instead of just any partitioning with pre-abortion in case of equal numbers.

If you search on stackoverflow, you'll find plenty of good ones, e.g.: https://stackoverflow.com/a/44209393/701049 (including a benchmark) or https://stackoverflow.com/a/18503368/701049 (from his EDIT).

I'd combine such a good one with the filter provided by Turn. If you want even more speed, you could also try to return None from the function in case of same numbers, and/or to write the partitioning in C-Code and compile it.

Combined it could look like this (accel_asc() copied from the link):

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def accel_asc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]

N = 20
unequal_partitions = [p for p in accel_asc(N) if len(p) == len(set(p))]
print unequal_partitions

You could also try to compile using Cython to make it even faster.

to find unequal partitions of an integer in php

2 Answers2