Python Forum
Avoid multiple repeat in indent
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Avoid multiple repeat in indent
#1
Hello,

I am trying to count the number of pairs but in the end i only want the variable count give the total.

import itertools

lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
    
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)

    return listo
    

  
  


def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                
printPairs(lim)
print('')
print('Primes sum that gives:', lim)
  

som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 
            print("Number of pairs: ", count)

            
            
            
Output:
Generate prime numbers up to : 10 2 3 5 7 Primes multiply that gives: 10 2 5 Primes sum that gives: 10 10 (3, 7) Number of pairs: 1 10 (2, 3, 5) Number of pairs: 2 >
Its only repeating number of pairs 1, 2 ...
I just want the total 2 pairs

Thank you
Reply
#2
Do you mean like this?
import itertools
 
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
     
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)
 
    return listo
     
 
   
   
 
 
def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                 
printPairs(lim)
print('')
print('Primes sum that gives:', lim)
   
 
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

print("Number of pairs: ", count)
Output:
Generate prime numbers up to : 10 2 3 5 7 Primes multiply that gives: 10 2 5 Primes sum that gives: 10 10 (3, 7) 10 (2, 3, 5) Number of pairs: 2
Reply
#3
Yes exactly i have done that but if i input 100 it wont return the number of pairs. Maybe its the compiler that has a limit.

Also is it possible to initialize the variable count at the top so that the numbers count appear just after Primes sum that gives:?

TY
Reply
#4
(Jan-17-2022, 04:46 PM)Frankduc Wrote: Also is it possible to initialize the variable count at the top so that the numbers count appear just after Primes sum that gives:?
Do you mean like this?
import itertools
  
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
      
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)
  
    return listo
      
def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                  
printPairs(lim)
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

print('')
print('Primes sum that gives:', lim)
print("Number of pairs: ", count)
Also, if you give it an 85 or 86 to chew on, you can see how long it takes. I think 100 is just overloading something.
Reply
#5
Primes up to 100 is not a big list.
Primes < 10 are 2, 3, 5, 7: 4 numbers
primes < 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97: 25 numbers

However, the number of possible combinations of these numbers grows very quickly.
Adding up all the combinations of the numbers in the primes(10) list taken 1 at a time, 2 at a time, 3 at a time and 4 at a time = 15 combinations.
The list of primes < 20 has only 8 numbers but 255 combinations.
The list of primes < 50 has 15 numbers and 32767 combinations.
The list of primes < 100 has 25 numbers and a wopping 33,554,431 combinations.

If n is the number of prime numbers, the number of combinations is 2^n - 1.

But this is not even the correct solution, because I don't see any prohibition against using 2*2*2 = 8, but (2,2,2) is not returned when you ask for all combinations of (2, 3, 5, 7) taken 3 at a time. To include combinations like (2, 2, 2) you need to use itertools.combinations_with_replacement(). Now primes < 10 has 69 combinations to test, primes < 20 has 12869 combinations, and I gave up when primes < 50 came up with 155,117,519 combinations.

I think the code below works and it is really efficient when compared to using combinations. products(100) recursively calls itself 99 times to compute the 1 product.

sums(100) calls itself 547,013 times to compute 48,899 sums. That means it finds a sum almost 1 in 10 tries. Using combinations you don't get all the sums and it only finds a sum about 1 in 1000 tries. Using combinations with replacement the hit to miss ration is probably around 1 in 1 million.
def prime_numbers(end):
    """Compute primes up to and including end using sieve of Eratosthenes algorithm"""
    primes = []
    not_primes = []
    end += 1
    for p in range(2, end):
        if p not in not_primes:
            primes.append(p)
            for np in range(p*p, end, p):
                not_primes.append(np)
    return primes

def products(target, choices, partial_product=1, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose product equals target.
    choices is list of numbers (here primes) that can be used as multiplicands.
    Save successful product lists in solutions.  Save partial product list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        products.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return products(target, choices, partial_product, [], [])

    products.count += 1
    for index, choice in enumerate(choices):
        attempt = values + [choice]
        if (product := partial_product * choice) < target:
            # Add choice as a multiplicand
            products(target, choices[index:], product, attempt, solutions)
        else:
            # Add solution if product == target.  Either way there are
            # no remaining solutions in this thread
            if product == target:
                solutions.append(attempt)
            break
    return solutions

def sums(target, choices, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose sum equals target.
    choices is list of values that can be used as addends.
    Save successful sum lists in solutions.  Save partial sum list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        sums.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return sums(target, choices, [], [])

    sums.count += 1
    sum_values = sum(values)
    for index, choice in enumerate(choices):
        # Add choice as addend
        attempt = values + [choice]
        if choice < target:
            sums(target-choice, choices[index:], attempt, solutions)
        else:
            # Add sum to solution if sum == target.  Either way there
            # are no solutions remaining in this thread.
            if choice == target:
                solutions.append(attempt)
            break
    return solutions

target = 100
primes = prime_numbers(target)
print("Products", target, products(target, primes), products.count)
print("Sums", target, len(sums(target, primes)), sums.count)
Reply
#6
(Jan-17-2022, 07:37 PM)BashBedlam Wrote:
(Jan-17-2022, 04:46 PM)Frankduc Wrote: Also is it possible to initialize the variable count at the top so that the numbers count appear just after Primes sum that gives:?
Do you mean like this?
import itertools
  
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
      
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)
  
    return listo
      
def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                  
printPairs(lim)
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

print('')
print('Primes sum that gives:', lim)
print("Number of pairs: ", count)
Also, if you give it an 85 or 86 to chew on, you can see how long it takes. I think 100 is just overloading something.

No i mean print: print("Number of pairs: ", count) above
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 
In C# you can place count = 0 at the top right after listo and than print wherever you want count.
Like this:

import itertools
count = 0
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
    
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)

    return listo
    

  
  


def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                
printPairs(lim)
print('')
print('Primes sum that gives:', lim)
print("Number of pairs: ", count) 
 

som = 0


for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 
but number of pairs will return 0.
Yes at 100 it is a lot. For now i am using an online compiler.
Reply
#7
(Jan-18-2022, 12:40 PM)deanhystad Wrote: Primes up to 100 is not a big list.
Primes < 10 are 2, 3, 5, 7: 4 numbers
primes < 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97: 25 numbers

However, the number of possible combinations of these numbers grows very quickly.
Adding up all the combinations of the numbers in the primes(10) list taken 1 at a time, 2 at a time, 3 at a time and 4 at a time = 15 combinations.
The list of primes < 20 has only 8 numbers but 255 combinations.
The list of primes < 50 has 15 numbers and 32767 combinations.
The list of primes < 100 has 25 numbers and a wopping 33,554,431 combinations.

If n is the number of prime numbers, the number of combinations is 2^n - 1.

But this is not even the correct solution, because I don't see any prohibition against using 2*2*2 = 8, but (2,2,2) is not returned when you ask for all combinations of (2, 3, 5, 7) taken 3 at a time. To include combinations like (2, 2, 2) you need to use itertools.combinations_with_replacement(). Now primes < 10 has 69 combinations to test, primes < 20 has 12869 combinations, and I gave up when primes < 50 came up with 155,117,519 combinations.

I think the code below works and it is really efficient when compared to using combinations. products(100) recursively calls itself 99 times to compute the 1 product.

sums(100) calls itself 547,013 times to compute 48,899 sums. That means it finds a sum almost 1 in 10 tries. Using combinations you don't get all the sums and it only finds a sum about 1 in 1000 tries. Using combinations with replacement the hit to miss ration is probably around 1 in 1 million.
def prime_numbers(end):
    """Compute primes up to and including end using sieve of Eratosthenes algorithm"""
    primes = []
    not_primes = []
    end += 1
    for p in range(2, end):
        if p not in not_primes:
            primes.append(p)
            for np in range(p*p, end, p):
                not_primes.append(np)
    return primes

def products(target, choices, partial_product=1, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose product equals target.
    choices is list of numbers (here primes) that can be used as multiplicands.
    Save successful product lists in solutions.  Save partial product list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        products.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return products(target, choices, partial_product, [], [])

    products.count += 1
    for index, choice in enumerate(choices):
        attempt = values + [choice]
        if (product := partial_product * choice) < target:
            # Add choice as a multiplicand
            products(target, choices[index:], product, attempt, solutions)
        else:
            # Add solution if product == target.  Either way there are
            # no remaining solutions in this thread
            if product == target:
                solutions.append(attempt)
            break
    return solutions

def sums(target, choices, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose sum equals target.
    choices is list of values that can be used as addends.
    Save successful sum lists in solutions.  Save partial sum list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        sums.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return sums(target, choices, [], [])

    sums.count += 1
    sum_values = sum(values)
    for index, choice in enumerate(choices):
        # Add choice as addend
        attempt = values + [choice]
        if choice < target:
            sums(target-choice, choices[index:], attempt, solutions)
        else:
            # Add sum to solution if sum == target.  Either way there
            # are no solutions remaining in this thread.
            if choice == target:
                solutions.append(attempt)
            break
    return solutions

target = 100
primes = prime_numbers(target)
print("Products", target, products(target, primes), products.count)
print("Sums", target, len(sums(target, primes)), sums.count)

Quick reply to deanHystad. I have not review all of the code. The code you provide are always interesting and a bit sophisticated for me.
Very informative that part about Mersenne prime. Interesting: https://en.wikipedia.org/wiki/Mersenne_prime

I am not sure about that part print("Sums", target, len(sums(target, primes)), sums.count)
Sums 10 5 18
18 stands for number of times it calculates to reach 10?
What about return sums(target, choices, [], []) what use have the [] ? idexation


Thank you
Reply
#8
[] is an empty list. It is being used exactly the same way you used [] in your program.
Reply
#9
(Jan-18-2022, 03:59 PM)deanhystad Wrote: [] is an empty list. It is being used exactly the same way you used [] in your program.

Ok so its the way to say that values and solutions are now list. Did not know we could do that.

I am a bit confuse. If i print("list of sums" ,sums(target,primes))

It will return :
list of sums [[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [3, 7], [5, 5]]
The primes are only 2,3,5,7
Why [2, 2, 2, 2, 2] should be included? List combination from primes under 10 is enough. Why invent new combinations? Of course you want to list all combinations possible that return 10. Is it still a prime combination if you repeat one prime numbers to satisfied the condition? Maybe we could investigate this.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  getting unexpected indent errors trying to move cells up jensengt 4 822 Jun-28-2023, 12:05 PM
Last Post: deanhystad
  xml indent SubElements (wrapping) with multiple strings ctrldan 2 1,383 Jun-09-2023, 08:42 PM
Last Post: ctrldan
  Why do I have to repeat items in list slices in order to make this work? Pythonica 7 1,258 May-22-2023, 10:39 PM
Last Post: ICanIBB
  Repeat request by else stsxbel 2 1,150 Jul-30-2022, 03:34 PM
Last Post: stsxbel
  IndentationError: unexpected indent dee 3 2,229 May-02-2022, 02:15 AM
Last Post: dee
  get out of while loop and stop repeat Frankduc 11 2,866 Apr-26-2022, 10:09 PM
Last Post: deanhystad
  How to discard list repeat values akanowhere 7 3,579 Dec-28-2020, 09:14 PM
Last Post: akanowhere
  I want to check if the input is str or is int & if it's str repeat the loop HLD202 4 2,723 Nov-23-2020, 11:01 PM
Last Post: perfringo
  IndentationError: unexpected indent jk91 1 2,339 Feb-27-2020, 08:56 PM
Last Post: buran
  is there a way: repeat key word args Skaperen 2 2,200 Feb-03-2020, 06:03 PM
Last Post: Skaperen

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020