algorithm - java - create a text file with all possible combinations of 0 and 1 (size n) -
i created text file via java. , file should contain possible combinations of 0 , 1 @ length n.
for example, combinations of n=3 are:
000,001,010,011,100,101,110,111
and file should contain:
000001010011110
and not:
000001010011100101110111
because algorithm checks if each combinations in file.
i have developed algorithm that, it's slow because of method check if combinations exist in file (infile()).
and cant use string may contain combinations, because if try generate length 20, length of string 2^20*20, , it's takes time eclipse analyze that.
the algorithm:
import java.io.bufferedreader; import java.io.bufferedwriter; import java.io.filenotfoundexception; import java.io.filereader; import java.io.filewriter; import java.io.ioexception; public class test { public static string filename = "file.txt"; public static int size = 20; public static filereader fr; public static bufferedreader br; public static filewriter fw; public static bufferedwriter bw; public static void main(string[] args) { try { fw = new filewriter(filename, true); bw = new bufferedwriter(fw); try { fr = new filereader(filename); br = new bufferedreader(fr); doit(size); system.out.println("\n>> finished"); br.close(); } catch(filenotfoundexception e) { system.out.println("file not found!"); } catch(ioexception e) { system.out.println("no file found!"); } bw.close(); } catch(filenotfoundexception e) { system.out.println("error1!"); } catch(ioexception e) { system.out.println("error2!"); } } public static void doit(int l) { string s="",c=""; for(int i=0;i<l;s+="0",c+="1",i++); write(s); while(!s.equals(c)) { for(int z=l-1;z>=0;z--) { if(s.charat(z) == '1') continue; s = s.substring(0,z); s += "1"; for(int b=0;b<l-z-1;b++) { s+="0"; } z=-1; } if(!infile(s)) { write(s); } } } public static boolean infile(string sub) { try { br = new bufferedreader(new filereader(filename)); string line = br.readline(); if(line.indexof(sub) != -1) return true; return false; } catch (filenotfoundexception e) { system.out.println("error: file read not found"); return false; } catch (ioexception e) { system.out.println("error: file read not found - 2"); return false; } } public static void write(string s) { try { bw.write(s); bw.flush(); } catch (ioexception e) { system.out.println("error3!"); } } } when length longer (more 20) it's getting worse. what should make faster?
thanks helping.
when generating bit-strings of length n, there n^2 possibilities. generate of these possibilities algorithmically, can generate bit-string each integer less n^2.
as in example of n = 3, 3^2 8 need use integers less 8: bit-string of length 3 0 000. bit-string of length 3 1 001. bit-string of length 3 2 010. bit-string of length 3 three 011. bit-string of length 3 4 100. bit-string of length 3 5 101. bit-string of length 3 6 110. bit-string of length 3 7 111.
we can generate these using following java method:
integer.tobitstring(4) will return "100". however, there problem, not pad number zeros reaches appropriate length.
integer.tobitstring(1) will return "1". solve this, can use java method pad integer appropriate number of spaces, , replace spaces 0's follow:
string.format("%3s", integer.tobinarystring(1)).replace(' ', '0') using loop, can generate , print these strings file
for(int = 0; < math.pow(2, n); i++) { string poss = string.format("%*s", n, integer.tobinarystring(i)).replace(' ', '0') fileprintstream.print(poss); } this generate every possible bit-string in order without duplicates.
Comments
Post a Comment