CODEWITHSUNDEEP
c++python
cb0
cb0

Reputation: 8613

Porting Python algorithm to C++ - different solution

Thank you all for helping. Below this post I put the corrected version's of both scripts which now produce the equal output.

Hello,

I have written a little brute string generation script in python to generate all possible combinations of an alphabet within a given length. It works quite nice, but for the reason I wan't it to be faster I try to port it to C++.

The problem is that my C++ Code is creating far too much combination for one word. Heres my example in python:

./test.py

gives me

aaa
aab
aac
aad
aa
aba
....

while ./test (the c++ programm gives me)

aaa
aaa
aaa
aaa
aa

Here I also get all possible combinations, but I get them twice ore more often.

Here is the Code for both programms:

 #!/usr/bin/env python
 import sys
 #Brute String Generator
 #Start it with ./brutestringer.py 4 6 "abcdefghijklmnopqrstuvwxyz1234567890" ""
 #will produce all strings with length 4 to 6 and chars from a to z and numbers 0 to 9
 def rec(w, p, baseString):
    for c in "abcd":
        if (p<w - 1):
            rec(w, p + 1, baseString + "%c" % c)
         print baseString

 for b in range(3,4):
     rec(b, 0, "")

And here the C++ Code

 #include <iostream>
 using namespace std;
 string chars="abcd";

 void rec(int w,int b,string p){
    unsigned int i;
    for(i=0;i<chars.size();i++){
        if(b < (w-1)){
            rec(w, (b+1), p+chars[i]);
        }
        cout <<  p << "\n"; 
    }
 }


 int main ()
 {
    int a=3, b=0;
    rec (a+1,b, "");
    return 0;
 }

Does anybody see my fault ? I don't have much experience with C++.

Thanks indeed

Here the corrected version:

C++

#include <iostream>
using namespace std;
string chars="abcd";

void rec(int w,int b,string p){
    unsigned int i;
    for(i=0;i<chars.size();i++){
        if(b < (w)){
            rec(w, (b+1), p+chars[i]);
        }
    }
    cout << p << "\n";
}


int main ()
{
    rec (3,0, "");
    return 0;
}

Python

#!/usr/bin/env python
import sys

def rec(w, b, p):
    for c in "abcd":
        if (b < w - 1):
            rec(w, b + 1, p + "%c" % c)
    print p

rec(4, 0, "")

Equal Output:

$ ./test > 1
$ ./test.py 3 3 "abcd" "" > 2
$ diff 1 2
$

Upvotes: 2

Views: 423

Answers (4)

user9876
user9876

Reputation: 11102

Just out of curiosity, is this fast enough?

import itertools, string
alphabet = string.lowercase + string.digits
for numchars in (3, 4):
    for x in itertools.product(alphabet, repeat=numchars):
        print ''.join(x)

(And make sure you're redirecting output to a file; scrolling huge amounts of text up the screen can be surprisingly slow).

Upvotes: 1

Alex Martelli
Alex Martelli

Reputation: 881695

You say...:

./test.py

gives me

aaa aab

(etc), but that's not true of the code you posted: what you get instead is 

aa
aa
aa
aa
a

with four repetitions of the leading aa, etc etc. Of course you do: you have the print baseString statement inside the loop of for c in "abcd":, so necessarily it's executed four times. I imagine you want that print out of the loop -- and similarly for the C++ code, where you've also put the output statement smack inside the loop, so it gets repeated.

Upvotes: 0

sth
sth

Reputation: 229603

In rec the string p gets printed in every iteration of the loop:

for(i=0;i<chars.size();i++){
    // ...
    cout <<  p << "\n"; 
}

The Python code you posted seems to do the same, but maybe there is something mixed up with the indentation there? Did you maybe mix tabs and spaces in the Python file, leading to surprising results?

Upvotes: 0

Aaron Digulla
Aaron Digulla

Reputation: 328614

I think the Python code is also broken but maybe you don't notice because the print is indented by one space too many (hey, now I've seen a Python program with a one-off error!)

Shouldn't the output only happen in the else case? And the reason why the output happens more often is that you call print/cout 4 times. I suggest to change the code:

def rec(w, p, baseString):
    if w == p:
        print baseString
    else:
        for ...

Upvotes: 1

Related Questions