Forum Archive

Hello pythonista community. Can someone adwise me formula for recognize quantity of unique combinations when you count to some max digit with sign "-" (minus)? Answer can't be under zero.

Example1:
sign = '-'
max = 2
2-2
2-1
1-1
- we have only three unique combinations.

Example2:
answer can't be upper max:
max = 2
1+1
- we have only one unique example.

I already have formula for two signs "+-": unic_col=max**2

But i need formula for '+' and '-'
And maybe someone know for:
+-×
+-/
+-×/
/×

So, i need function like that:

def uniques_col(operators, max):
if operators == '+-':
return max**2
elif operators == '+':
return .....
elif operators == '-':
return .....
elif operators == '+-×':
return .....
......

@lyubomyr83, I am confused by the problem definition. What is max?

• Largest digit to be used in the calculations, or
• largest allowed result of a calculation, or
• both of the above?

Also, what do you need this for?

@mikael
Max - variable count to, for example 100.
So i need count quantity uniques examples for some mathematic operator, in my case '+' or '-'
I can't have example 98+10 or 25-50
Max example result must be under 100 or equal
Minimum example result must be under 0

@lyubomyr83 said:

Minimum example result must be under 0

upper 0

@lyubomyr83 sorry if I didn't understand correctly, do you want a formula or a script like

def uniques_col(operators, max):
    n = 0
    if operators == '+':
        for i in range(1,max):
            for j in range(i,max-i+1):
                n += 1
                print(i,operators,j,'=',i+j)
    elif operators == '-':
        for i in range(1,max+1):
            for j in range(1,i+1):
                n += 1
                print(i,operators,j,'=',i-j)
    return n

op = input('operator')
v = int(input(op))
print(uniques_col(op,v))

@lyubomyr83 Something like this?

# -*- coding: utf-8 -*-
"""
Test solution for https://forum.omz-software.com/topic/6159/function-for-recognize-quantity-of-unique-combinations
"""
import operator


OPERATORS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "×": operator.mul,
}


def eval_eq(a, op, b):
    return OPERATORS[op](a, b)


def uniques_col(operators, max):
    if len(operators) == 0:
        # we could also just return (max - 1)
        raise ValueError("No operators given!")
    elif len(operators) > 1:
        # the code in the question makes it look like we should add
        # the number of individual operator combinations if multiple
        # operators are given.
        n = 0
        for op in operators:
            n += uniques_col(op, max)
        return n
    else:
        combinations = []
        for a in range(max, 0, -1):
        # for a in range(1, max + 1):
            for b in range(max, 0, -1):
            # for b in range(1, max + 1):
                res = eval_eq(a, operators, b)
                if res > max:
                    # should this be result >= max?
                    continue
                if res < 0:
                    # result cant be under 0
                    continue
                comb = (a, operators, b)
                print(comb)
                if comb not in combinations:
                    combinations.append(comb)
        return len(combinations)


if __name__ == "__main__":
    testdata = [
        # format: operators, max, expected
        ("-", 2, 3),
        ("+", 2, 1),
        ("+-", 2, 4),
        ("+-", 3, 9),
        ("+-*", 3, None),
    ]
    for ops, m, exp in testdata:
        n = uniques_col(ops, m)
        print("uniques_col({m}, '{o}') -> {r}; expected {e}".format(m=m, o=ops, r=n, e=exp))

This produced this output:

(2, '-', 2)
(2, '-', 1)
(1, '-', 1)
uniques_col(2, '-') -> 3; expected 3
(1, '+', 1)
uniques_col(2, '+') -> 1; expected 1
(1, '+', 1)
(2, '-', 2)
(2, '-', 1)
(1, '-', 1)
uniques_col(2, '+-') -> 4; expected 4
(2, '+', 1)
(1, '+', 2)
(1, '+', 1)
(3, '-', 3)
(3, '-', 2)
(3, '-', 1)
(2, '-', 2)
(2, '-', 1)
(1, '-', 1)
uniques_col(3, '+-') -> 9; expected 9
(2, '+', 1)
(1, '+', 2)
(1, '+', 1)
(3, '-', 3)
(3, '-', 2)
(3, '-', 1)
(2, '-', 2)
(2, '-', 1)
(1, '-', 1)
(3, '*', 1)
(2, '*', 1)
(1, '*', 3)
(1, '*', 2)
(1, '*', 1)
uniques_col(3, '+-*') -> 14; expected None

Your question is kind of hard to understand, so I am not sure this solution is correct...

@bennr01, nice! Couple of possible, nit-picky refinements:

Do not use max as an argument name.

Instead of for loops, generate the candidates with:

candidates = itertools.product(
    range(max_int+1), operations, range(max_int+1)
)

@mikael said:

Do not use max as an argument name.

Generally true, but in this case I wanted to preserve the original function signature used in the question.

Instead of for loops, generate the candidates with:

candidates = itertools.product(
    range(max_int+1), operations, range(max_int+1)
)

Yeah, that is way cleaner.

@bennr01, just read an article on functional programming in Python, so one step further:

import itertools
import operator

OPERATORS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "×": operator.mul,
}

def uniques_col(operators, max_value):
    return filter(
        lambda c: 0 <= OPERATORS[c[1]](c[0], c[2]) <= max_value,
        itertools.product(
            range(1, max_value+1),
            operators,
            range(1, max_value+1)
        )
    )

print(list(uniques_col('+-', 2)))

@lyubomyr83, not an answer to your question, but maybe you can use these brute-force versions to check the formulas you come up with?

@bennr01, with one more fancy function:

import itertools

def uniques_col(operators, max_value):
    possibles = lambda: range(1, max_value+1)
    return filter(
        lambda c: 0 <= eval(''.join(map(str, c))) <= max_value,
        itertools.product(possibles(), operators, possibles())
    )

print(list(uniques_col('+-', 2)))

@cvp, thank you all for help!!!
With your function i receive right col for '-', but not for '+':

def uniques_col(operators, max):
n = 0
if operators == '+':
for i in range(1,max):
for j in range(i,max-i+1):
n += 1
print(i,operators,j,'=',i+j)
elif operators == '-':
for i in range(1,max+1):
for j in range(1,i+1):
n += 1
print(i,operators,j,'=',i-j)
return n

while True:
op = input('operator\n')
max = int(input('max\n'))
print(uniques_col(op,max))

What i receive:
operator-
max4
1 - 1 = 0
2 - 1 = 1
2 - 2 = 0
3 - 1 = 2
3 - 2 = 1
3 - 3 = 0
4 - 1 = 3
4 - 2 = 2
4 - 3 = 1
4 - 4 = 0
10
operator+
max4
1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
2 + 2 = 4
4

Where is 1+3 and 2+1, so for '+' i need receive 6 unique examples.

@lyubomyr83 said:

Where is 1+3 and 2+1,

Ok, I did believe that 1+2 is the same as 2+1, thus I did not generate it.
As I told you, I was not sure to correctly understand 😀

Thus it is better to use the other script (of @bennr01 and @mikael ) because it tries all combinations.

@lyubomyr83

Or Change into

    if operators == '+':
        for i in range(1,max):
            for j in range(1,max-i+1): 

i think you would want to check 1 to max for both numbers (consider /, max/max=1)

@JonB if you do that, you have to check and skip cases where i+j>max
With « my » formula, no check is needed

Combinatoric iterators:
* https://docs.python.org/3/library/itertools.html#itertools.combinations
* https://docs.python.org/3/library/itertools.html#itertools.combinations_with_replacement
* https://docs.python.org/3/library/itertools.html#itertools.permutations

@ccc I'm always positively surprised by the number of libraries in Python

I went into some kind of half-insane readability/conciseness optimization/noodling loop on this. Here’s the latest version:

from itertools import product

def uniques_col(ops, maximum):
    number_range = range(1, maximum+1)
    numbers = list(map(str, number_range))
    return filter(
        lambda c: 0 <= eval(''.join(c)) <= maximum,
        product(numbers, ops, numbers)
    )

uniques = uniques_col('+-/', 2)

print(*[
    f"{i+1:4}: {''.join(c)}"
    for i, c in enumerate(uniques)],
    sep='\n'
)

numbers = [str(i + 1) for i in range(maximum)]

Read “What’s new in Python 3” for a discussion on avoiding map(), reduce(), filter().

@ccc, you take the prize for conciseness, and readability is not bad either.

I was debating the value of separating the range of numbers (problem domain issue) and the conversion to strings (a technical implementation detail).

@mikael and @ccc I think that I'll stop to believe I can program in Python 😢

@ccc said:

What’s new in Python 3

For clarity, What’s new in Python 3 does not advice against using map and filter as such, but against using list(map(...)) when a list comprehension can be used instead.

Thus, as already said, your amendment makes a lot of sense, but it does not automatically follow that we would change the filter into a comprehension, if we want to leave it up to the user of the function to decide whether to ”collapse” the iterator or not.

@cvp, ha ha. There’s a huge difference and swiftly diminishing returns between ”getting to results” and ”getting to perfect”. While this kind of noodling is fun (for me), your recent track record of real results speaks for itself.

@mikael you're too kind 😳

@cvp thank's a lot. It working for '+', '-' and '+-':

def uniques_col(operators, max):
    col = 0
    if operators == '+':
        for i in range(1,max):
            for j in range(1,max-i+1):
                col += 1
    elif operators == '-':
        for i in range(1,max+1):
            for j in range(1,i+1):
                col += 1
    elif operators == '+-':
            col = max**2

    return col


while True:
    op = input('operator\n')
    max = int(input('max\n'))
    print(uniques_col(op,max))

And maybe you know uniques col for:
+-×
+-/
+-×/
/×

??? Thank's in advance!!!

@lyubomyr83, this code:

from itertools import product

def uniques_col(ops, maximum):
    numbers = [str(i+1) for i in range(maximum)]
    return filter(
        lambda c: 0 <= eval(''.join(c)) <= maximum,
        product(numbers, ops, numbers)
    )

ops_list = ['+-*', '+-/', '+-/*', '/*']
to_limit = 20

for ops in ops_list:
    print('-'*20)
    print('ops', ops)
    for maximum in range(1, to_limit+1):
        print(maximum, len(list(
            uniques_col(ops, maximum))))

... gives series up to 20 for each set of operations. For +-/, I can deduct that the formula for possibilities is 2*max*max. For the others, not as easy, need to dig out a maths book or two.

@lyubomyr83 please try this and tell us if non integer result is allowed for division

def uniques_col(operators, max):
    col = 0
    if len(operators) > 1:
        for op in operators:
            col += uniques_col(op, max)
        return col
    if operators == '+':
        for i in range(1,max):
            for j in range(1,max-i+1):
                print(i,operators,j,i+j)
                col += 1
    elif operators == '-':
        for i in range(1,max+1):
            for j in range(1,i+1):
                print(i,operators,j,i-j)
                col += 1
    elif operators == 'x':
        for i in range(1,max+1):
            for j in range(1,1+int(max/i)):
                print(i,operators,j,i*j)
                col += 1

    return col

while True:
    op = input('operator\n')
    max = int(input('max\n')) 

@lyubomyr83, here’s a version that tries to be smart where possible. Unfortunately, finding the number of unique combinations for multiplication * seems to be directly related to finding the factors of an integer, for which there is no straight-forward formula (hence, public key cryptography works), so we still have to brute-force it.

from functools import reduce
from itertools import product

def unique_cols(ops, maximum):

    counts = {
        '-': lambda m: m*(m+1)//2,
        '+': lambda m: m*(m-1)//2,
        '/': lambda m: m**2,
        '*': lambda m: len(list(filter(
            lambda c: 0 <= eval(''.join(c)) <= m,
            product([str(i+1) for i in range(m)], '*', [str(i+1) for i in range(m)])
        )))
    }
    return sum([counts[op](maximum) for op in ops])

maximum = int(input('Maximum integer: '))
ops = input('Operations (one of more of +-*/): ')

print('Unique combinations:', unique_cols(ops, maximum))

For multiplication, it seems the number would be something like this:. Consider building the 2d multiplication table, 1..N in cold and rows. Then count how many you have in each row that are <=N. To avoid double counting, handle the diagonal separately.

For each row of the multiplication table, excluding the diagonal, you get

1*x (x!=1)    ==>  N-1 different possiblities
2*x (x!=2)    ==>  (N//2)-1
...
K*x  (x!=K)    ==>  (N//k)-1

Then for the diagonal, it is the number of x**2<N
Or, x<=sqrt(N)

So the total is:

sum([(N//k) for k in range(1,N+1)])-N+floor(sqrt (N) )

Or

sum([(N//k) for k in range(2,N+1)])+floor(sqrt (N) )

Not quite brute force, but order N instead of N**2. You could also make use of the symmetry to only count through sqrt(N), which makes it order sqrt (N)..

```
2*sum([(N//k)-k for k in range(1,1+floor(sqrt(N))])+floor(sqrt (N) )

@JonB, impressive! Need to spend some more time to really follow the logic, but the results match with the brute-force results, so here is the updated version:

from itertools import product
from math import floor, sqrt

def unique_cols(ops, maximum):

    counts = {
        '-': lambda m: m*(m+1)//2,
        '+': lambda m: m*(m-1)//2,
        '/': lambda m: m**2,
        '*': lambda m:
            2 * sum([(m//k)-k
                for k in range(1, 1 + floor(sqrt(m)))]) +
            floor(sqrt(m)),
    }
    return sum([counts[op](maximum) for op in ops])


maximum = int(input('Maximum integer: '))
ops = input('Operations (one of more of +-*/): ')

print('Unique combinations:', unique_cols(ops, maximum))

@mikael shouldn't + and - be the same? In the table of allowables, in the subtraction case you are allowed everything above the diagonal that is along (1,1) to (N,N) (assuming zero is not allowed?). In the plus case, everything above the other diagonal. So both cases are (NN-N)/2==N(N-1)/2

I guess it depends on whether you allow 1-1=0 and the like. If so you'd add back N, and get N*(N+1)/2.

@JonB for multiplication, do you think it is different of mine

        for i in range(1,max+1):
            col += int(max/i) 

@cvp, oh my goodness, my apologies, it looked so simple I did not even understand it is a solution. Which also checks against the brute-force values, hence the simplified version below.

@JonB, yes, we include 1-1 as per the ”rules”.

def unique_cols(ops, maximum):

    counts = {
        '-': lambda m: m*(m+1)//2,
        '+': lambda m: m*(m-1)//2,
        '/': lambda m: m**2,
        '*': lambda m: sum([m//i for i in range(1, m+1)]),
    }
    return sum([counts[op](maximum) for op in ops])


maximum = int(input('Maximum integer: '))
ops = input('Operations (one or more of +-*/): ')

print('Unique combinations:', unique_cols(ops, maximum))

@mikael said:

it looked so simple

Haha 😂

As terribly interesting as this has been, I am still wondering what it is for...

My last version, still without division due to an unanswered question

def uniques_col(operators, max):
    col = 0
    if len(operators) > 1:
        for op in operators:
            col += uniques_col(op, max)
        return col
    if operators == '+':
        for i in range(1,max):
            col += max - i
            # comment next lines if you don't want detail
            for j in range(1,max-i+1):
                print(i,operators,j,i+j)
    elif operators == '-':
        for i in range(1,max+1):
            col += i
            # comment next lines if you don't want detail
            for j in range(1,i+1):
                print(i,operators,j,i-j)
    elif operators == 'x':
        for i in range(1,max+1):
            col += int(max/i)
            # comment next lines if you don't want detail
            for j in range(1,1+int(max/i)):
                print(i,operators,j,i*j)

    return col

while True:
    op = input('operator\n')
    max = int(input('max\n'))
    print(uniques_col(op,max))