LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 06-30-2017, 12:02 PM   #91
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319

Quote:
Originally Posted by norobro View Post
Python executes those combinations pretty quickly using the intertools module. https://docs.python.org/3/library/itertools.html
Python's itertools.combinations_with_replacement() is nice, but I decided to make my own sequential combination generator. It is a short recursive function. It uses the previous combination to generate the next combination in the sequence. Here is a sample program in Python:
Code:
# comb_rep.py
# program to test a combination-with-replacement generator

def next_comb_rep(array, place, base):
    if place == 0:
        array[place] += 1
    elif next_comb_rep(array, place-1, base):
        array[place] += 1
        for i in range(place):
            array[i] = array[place]
    return array[place]==base
    
base = int(input("How many choices? "))
size = int(input("How many items to choose? "))
digits = size*[0]

while True:
    print(digits)
    if next_comb_rep(digits, size-1, base):
        break
Here is the result of a small test:
Code:
How many choices? 3
How many items to choose? 3
[0, 0, 0]
[1, 0, 0]
[2, 0, 0]
[1, 1, 0]
[2, 1, 0]
[2, 2, 0]
[1, 1, 1]
[2, 1, 1]
[2, 2, 1]
[2, 2, 2]
 
Old 06-30-2017, 12:07 PM   #92
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Finally I used combinations to find Armstrong numbers. It is pretty fast, even in this Python implementation:
Code:
# armstrong_by_combinations.py  
# program to find Armstrong numbers
# using a sequential combination-with-replacement generator

def next_comb_rep(array, place, base):
    if place == 0:
        array[place] += 1
    elif next_comb_rep(array, place-1, base):
        array[place] += 1
        for i in range(place):
            array[i] = array[place]
    return array[place]==base

def sum_of_power_of_digit_array(digits):
    power = len(digits)
    psum = 0
    for d in digits:
        psum += d**power
    return psum

base = 10

for size in range(3,12):
    print("\n", size, ":", sep="")
    digit_array = size*[0]
    while True:
        if next_comb_rep(digit_array, size-1, base):
            break
        n = sum_of_power_of_digit_array(digit_array)
        n_digits = [int(x) for x in str(n)]
        n_digits.sort(reverse=True)
        if n_digits == digit_array:
            print(n)
And here is a timed test:
Code:
time python3 armstrong_by_combinations.py

3:
370
407
153
371

4:
8208
1634
9474

5:
93084
92727
54748

6:
548834

7:
9800817
4210818
1741725
9926315

8:
24678050
24678051
88593477

9:
146511208
912985153
472335975
534494836

10:
4679307774

11:
32164049650
40028394225
42678290603
49388550606
32164049651
94204591914
44708635679
82693916578

real	0m8.814s
user	0m8.808s
sys	0m0.000s
 
Old 06-30-2017, 10:49 PM   #93
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
Now we have to do it in assembly!
 
Old 07-01-2017, 01:21 AM   #94
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
In the meantime, I did it in Perl using the caching algorithm for all powers. It is amazingly fast!

Code:
#!/usr/bin/perl

#build hash table of powers

my %powerhash = ();

for (my $a = 0; $a < 10; $a++) {
   for (my $b = 0; $b < 10; $b++) {
      $powerhash{$a}{$b} = $a ** $b; 
   }
}

# Look for 3-digit Narcissitic Numbers (Armstrong Numbers)

for (my $a = 0; $a < 10; $a++) {
   for (my $b = 0; $b < 10; $b++) {
       for (my $c = 0; $c < 10; $c++) {
            my $value = $a * 100 +  $b * 10 + $c;
            my $powersum = $powerhash{$a}{3} + $powerhash{$b}{3} + $powerhash{$c}{3};
            if ($value == $powersum) {
               printf "%03d is an Armstrong number\n", $value;
            }
       }
   }
}

Output:

Code:
| => ./perlarm.pl 
000 is an Armstrong number
001 is an Armstrong number
153 is an Armstrong number
370 is an Armstrong number
371 is an Armstrong number
407 is an Armstrong number

Last edited by Laserbeak; 07-01-2017 at 01:24 AM.
 
Old 07-01-2017, 03:06 AM   #95
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
Quote:
Originally Posted by Beryllos View Post
...
10:
4679307774
...
real 0m8.814s
user 0m8.808s
sys 0m0.000s
[/CODE]
For me it took 3-4 minutes to find this number (in c). Probably I could improve it and will be able to complete under 1 minute, but this looks still much better. And we can still go further, using multithreaded/multicore environment.
 
Old 07-01-2017, 03:27 AM   #96
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
I'd like someone do it in a pure shell script lol.
 
Old 07-01-2017, 03:35 AM   #97
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
In Perl, you can actually use Berkeley DB (or even a SQL database) as backing for hashes and save the results of the hash of powers (and even already-calculated Narcissistic Numbers) so you don't have to recalculate them every time, so you could make it that after the first time you ran it, the results would be saved and you could work on making the rest of the application more thorough without having to recalculate what you've already done successfully again.
 
Old 07-01-2017, 04:00 AM   #98
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
Two improvements:
Quote:
Originally Posted by Beryllos View Post
Code:
# armstrong_by_combinations.py  
# program to find Armstrong numbers
# using a sequential combination-with-replacement generator

def next_comb_rep(array, place, base):
    if place == 0:
        array[place] += 1
    elif next_comb_rep(array, place-1, base):
        array[place] += 1
        for i in range(place):
            array[i] = array[place]
    return array[place]==base

# do not need to calculate power, it is known
def sum_of_power_of_digit_array(digits, power):
#    power = len(digits)
    psum = 0
    for d in digits:
        psum += d**power
    return psum

base = 10

for size in range(3,12):
    print("\n", size, ":", sep="")
    digit_array = size*[0]
    while True:
        if next_comb_rep(digit_array, size-1, base):
            break
        n = sum_of_power_of_digit_array(digit_array, size)
        if (len(str(n)) != size):
            continue
        n_digits = [int(x) for x in str(n)]
        n_digits.sort(reverse=True)
        if n_digits == digit_array:
            print(n)
passing the size gave less than 1% improvement, but checking the size is much faster than checking the digits, that means at about 10% faster execution (at least for me).

additionally, using an array instead of power function will dramatically improve the performance:
Code:
    powers=[]
    for x in range(11):
        powers.append(x**size)
....
def sum_of_power_of_digit_array(digits, power):
    psum = 0
    for d in digits:
        psum += powers[d]
    return psum
This is a very compact solution anyway, I like it.

Last edited by pan64; 07-01-2017 at 05:46 AM.
 
Old 07-01-2017, 03:18 PM   #99
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
Here is a full solution to the Narcissistic Numbers problem written in Perl:

Code:
#!/usr/bin/perl

my $MAX_DIGITS = 10;


#build hash table of powers

my %powerhash = ();

for (my $a = 0; $a < 10; $a++) {
   for (my $b = 0; $b < 10; $b++) {
      $powerhash{$a}{$b} = $a ** $b; 
   }
}

#Find the Narcissistic Numbers

for $num_digits (1..$MAX_DIGITS) {
  print "\n\nCalculating narcissistic numbers with $num_digits digits.\n\n";
  
  my $minnum = "1" . "0" x ($num_digits - 1);
  my $maxnum = "9" x $num_digits;
  for ($testnum = $minnum; $testnum <= $maxnum; $testnum++) {
      @digits = split //, $testnum;
      @digits_power = ();
      for (0 .. $#digits) {
          $digits_power[$_] = $powerhash{$digits[$_]}{$num_digits}; 
      }
      my $sum = 0;
      for (@digits_power) {
          $sum += $_;
      }
      if ($testnum == $sum) {
          my $format_string = "%0" . $num_digits . "d" . " is a narcisstic number.\n";
          printf $format_string, $testnum;
       }
   }
}

exit (0);

Last edited by Laserbeak; 07-01-2017 at 03:32 PM. Reason: spelling
 
Old 07-01-2017, 08:28 PM   #100
norobro
Member
 
Registered: Feb 2006
Distribution: Debian Sid
Posts: 792

Rep: Reputation: 331Reputation: 331Reputation: 331Reputation: 331
I converted Beryllos' algorithm to c++ and it runs very quickly.

For example:
Code:
1 digits:
1
2
3
4
5
6
7
8
9

...
...

10 digits:
4679307774

11 digits:
32164049650
40028394225
42678290603
49388550606
32164049651
94204591914
44708635679
82693916578

real    0m0.282s
user    0m0.276s
sys     0m0.004s
Twenty digits will overflow an unsigned long long (2^64 == 8^20*2) so a large number library is neccessary. Using libgmp slows processing considerably, at least with my code.

Using usigned long long:
Code:
19 digits:
1517841543307505039
3289582984443187032
4929273885928088826
4498128791164624869

real    0m11.977s
user    0m11.968s
sys     0m0.000s
Using libgmp:
Code:
19 digits:
1517841543307505039
3289582984443187032
4929273885928088826
4498128791164624869

real    0m51.818s
user    0m51.792s
sys     0m0.004s
I'll post my code if anyone is interested.
 
Old 07-02-2017, 01:06 AM   #101
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 143Reputation: 143
Quote:
Originally Posted by norobro View Post
I'll post my code if anyone is interested.
Sure...

I was just thinking C++ has a lot of the tricks I used the Perl version and would run much faster.
 
Old 07-02-2017, 03:22 AM   #102
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
you ought to sort the result
Code:
11 digits:           sorted
32164049650      32164049650
40028394225      32164049651
42678290603      40028394225
49388550606      42678290603
32164049651      44708635679
94204591914      49388550606
44708635679      82693916578
82693916578      94204591914
 
Old 07-02-2017, 07:20 AM   #103
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by pan64 View Post
you ought to sort the result
Code:
11 digits:           sorted
32164049650      32164049650
40028394225      32164049651
42678290603      40028394225
49388550606      42678290603
32164049651      44708635679
94204591914      49388550606
44708635679      82693916578
82693916578      94204591914
Yes, I noticed that my numbers came out in order of the permutations. I could sort them at the end.
 
Old 07-02-2017, 09:34 AM   #104
norobro
Member
 
Registered: Feb 2006
Distribution: Debian Sid
Posts: 792

Rep: Reputation: 331Reputation: 331Reputation: 331Reputation: 331
Here is the "unsigned long long int" version which is basically a conversion of Beryllos' python code in post #42.
Code:
#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::vector;
typedef unsigned long long ull;

bool next_comb_rep(vector<ull> &vec, int place) {
    if(place == 0){
        vec[place] += 1;
    } else {
        if(next_comb_rep(vec, place-1)) {
            vec[place] += 1;
            for(int j=0; j<place; ++j) {
                vec[j] = vec[place];
            }
        }
    }
    return vec[place]==10;
}

ull sum_of_power_of_digit(vector<ull> &digits) {
    unsigned power = digits.size();
    ull sum = 0;
    for(unsigned i=0; i<power; ++i) {
        ull res = 1;
        unsigned digit = digits[i];
        for(unsigned pow=0; pow<power; ++pow) {
            res *= digit;
        }
        sum += res;
    }
    return sum;
}

int main() {
    for(int i=1; i<12; ++i) {
        cout << "\n" << i << " digits:\n";
        vector<ull> vec(i);
        vector<ull> out_vec;
        while(1){
            if(next_comb_rep(vec, i-1)) {
                break;
            }
            ull num = sum_of_power_of_digit(vec);
            ull tmp_num = num;
            vector<ull> tmp;
            while(tmp_num>0){
                tmp.emplace_back(tmp_num % 10);
                tmp_num /=10;
            }
            sort(tmp.begin(), tmp.end(), [](const ull a, const ull b) {return a > b; });
            if(tmp == vec) {
                out_vec.emplace_back(num);
            }
        }
        std::sort(out_vec.begin(), out_vec.end()); 
        for(ull i : out_vec){
            cout << i << "\n";
        }
    }
}
Quote:
Originally Posted by pan64 View Post
you ought to sort the result
Agreed. I mistakenly used an older version. for the 11 digit run. Notice that the 19 digit results are in order.

Last edited by norobro; 07-04-2017 at 09:50 PM. Reason: Note to self: have eyes checked. 19 digit results are not sorted.
 
Old 07-02-2017, 10:33 AM   #105
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
and again, using an array instead of recalculating powers will significantly increase the speed:
Code:
include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::vector;
typedef unsigned long long ull;

static vector<ull> powers(12);

bool next_comb_rep(vector<ull> &vec, int place) {
    if(place == 0){
        vec[place] += 1;
    } else {
        if(next_comb_rep(vec, place-1)) {
            vec[place] += 1;
            for(int j=0; j<place; ++j) {
                vec[j] = vec[place];
            }
        }
    }
    return vec[place]==10;
}

ull sum_of_power_of_digit(vector<ull> &digits, int power) {
    ull sum = 0;
    for(int i=0; i<power; ++i) {
        sum += powers[digits[i]];
    }
    return sum;
}

int main() {
    for(int base=1; base<20; ++base) {
        cout << "\n" << base << " digits:\n";
        vector<ull> vec(base);
        vector<ull> out_vec;
        for (int i=1; i<12; i++) {
             powers[i] = i;
             for(int pow=1; pow<base; ++pow) {
                 powers[i] *= i;
             }
       }
        while(1){
            if(next_comb_rep(vec, base-1)) {
                break;
            }
            ull num = sum_of_power_of_digit(vec, base);
            ull tmp_num = num;
            vector<ull> tmp;
            while(tmp_num>0){
                tmp.emplace_back(tmp_num % 10);
                tmp_num /=10;
            }                       // <= line 60
            sort(tmp.begin(), tmp.end(), [](const ull a, const ull b) {return a > b; });
            if(tmp == vec) {
                out_vec.emplace_back(num);
            }
        }
        std::sort(out_vec.begin(), out_vec.end());
        for(ull i : out_vec){
            cout << i << "\n";
        }
    }
}
with power function 23 seconds, with array 15.5, with additional length check it was again almost 10% faster (14.4)
Code:
# after line 60
           if (tmp.size() != (unsigned)base )
                 continue;
Furthermore adding a function:
Code:
bool del (vector<ull> &v, int i) {
    auto it = std::find(v.begin(), v.end(), i);
    if(it == v.end())
        return false;
    v.erase(it);
    return true;
}
and replacing the while loop:
Code:
       while(1){
            if(next_comb_rep(vec, base-1)) {
                break;
            }
            ull num = sum_of_power_of_digit(vec, base);
            ull tmp_num = num;
            vector<ull> vec1 = vec;
            while(tmp_num>0){
                if ( ! del(vec1, tmp_num % 10) )
                    break;
                tmp_num /=10;
            }
            if (vec1.size() != 0 )
                 continue;
            out_vec.emplace_back(num);
        }
will lead to 3.4 sec, which is approximately 15% of "original" execution time.
 
2 members found this post helpful.
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
printing line numbers for code bauer172uw Programming 3 04-13-2006 11:10 PM
C programming - sorting random numbers Gigantor Programming 8 12-05-2005 10:32 PM
Printing numbers from a text file dynamically mrobertson Programming 1 06-28-2005 08:19 AM
printing numbers without using semicolon vijeesh_ep Programming 18 09-08-2004 11:59 AM
printing line numbers? fisheromen1031 Programming 1 07-27-2004 02:19 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 02:44 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration