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 C开发者_如何学Pythonode 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
$
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 ...
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).
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?
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.
精彩评论