☰

» »

[java] kombinacije

[java] kombinacije

Yacked2 ::

Pozdravljeni,
izdelujem program, ki mora v določenem koraku izpisati vse kombinacije arrayev.
Primer:
String[] stevila = new String[3];
stevila[0] = "123";
stevila[1] = "34";
stevila[2] = "346";

Sedaj me zanima, kako bi spisal program, ki bi mi zgeneriral vse možne kombinacije nizov, kjer je prva števka iz [0], druga iz [1], tretja iz[2]. V posameznem delu bo največ 9 številk, skupaj pa bo array stevila velik do 81 elementov.

Primer za String[] stevila = new String[] {"123","23"}

bi program moral izpisati: "12","22","32","13","23","33".

Hvala za pomoč!

edit: dodana slika

Korak naprej ni vedno ustrezen...sploh če si na robu prepada!
  • spremenil: Yacked2 ()

mallard ::

Največ 81 elementov po največ 9 znakov. Torej v najslabčem primeru 9^81 kombinacij. Si prepričan, da hočeš vse izpisat?

ragezor ::

a je to za faks naloga?
btw tole niso kombinacije ampak produkt
ce ni:
import itertools

result = list(itertools.product('123', '23', '456', ...))
print result


tole je v pythonu ampak v javi je verjetno kaka podobna knjiznica

ce mas pa za faks bos pa moral uporabljati for zanke

za namig ti pokazem tole
for i in '123':
    for j in '23':
        print i+j

tole je za dva arraya. ce mas 9 arrayov das 9 for loopov zapored. na tebi pa je, da zdaj uporabis kak trik in napises kodo, ki hendla n arrayov.

Yacked2 ::

Moja rešitev:
public class bf {

    public static void main(String[] args) {
    	String[] cifre = new String[]{"232","34","65"};
    	char[] kombinacija = new char[cifre.length];

    	int moc = 1;
    	
    	for(String a :cifre)
    	{
    		moc = moc* a.length();
    	}

    	
    	int[] stopnje = new int[cifre.length];	
    	for(int i =0; i<stopnje.length;i++)
    	{
    		stopnje[i] = 0;
    	}
    	
    	for(int a=0; a < stopnje.length;a++)
		{
    		kombinacija[a] = cifre[a].charAt(0);
			
		}
		for(char b:kombinacija)
		{
			System.out.print(b);
		}
		System.out.println();
    	
    	for (int i=0; i < moc-1; i++)
    	{
    		if(stopnje[0] +1 < cifre[0].length())
    		{
    			stopnje[0] +=1;
    		}
    		else
    		{
    			int dolzina = cifre.length;
    			
    			for(int k=1; k < dolzina;k++)
    			{
    				if(stopnje[k] +1 < cifre[k].length())
    				{
    					stopnje[k] += 1;
    					for(int b=0; b <k; b++)
    					{
    						stopnje[b]=0;
    					}
    					break;
    				}
    			}
    		}
    		for(int r=0; r<stopnje.length;r++)
    		{
    			//String abc = Integer.toString(stopnje[r]);
    			kombinacija[r] = cifre[r].charAt(stopnje[r]);
    			//System.out.print(abc);
    		}
    		
    		for(char bb: kombinacija)
    		{
    			System.out.print(bb);
    		}
    		
    		System.out.println();
    	}
    
    		    	
    }

}


Na sudoku se bom z bruteforcom spravil :)
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

Yacked2 ::

mallard je izjavil:

Največ 81 elementov po največ 9 znakov. Torej v najslabčem primeru 9^81 kombinacij. Si prepričan, da hočeš vse izpisat?


Ne, izpisal bom samo ta pravilno
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

technolog ::

Uporabi rekurzijo oz. simulacijo rekurzije s skladom.

Yacked2 ::

Jap, res bo treba malo zoptimizirati program, mi že od 15te ure računa en sudoku.
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

ragezor ::

ja ocitno z bruteforce pristopom ne bo slo

mogoce se ti zdi, da je od 15te ure ze dosti casa preteklo ampak lahko ti povem, da za casa nasih zivljenj ne bos dobil resitve. niti za casa zivljenj tvojih otrok in vnukov ne in tako dalje :)

Spura ::

Bruteforce bi verjetno delal ce bi mel osnovni backtracking, tole k je pa napisan pa niti ne razumem kako dela. Moral bi sledit katere cifre mas v vrstici, stolpcu in kvadratu ze in backtrackat tkoj k rata nemogoce, da nadaljujes.

Spura :: 

public class Test {
	
    private static byte[][] start = new byte[9][9];
    private static int[] rows = new int[9];
    private static int[] cols = new int[9];
    private static int[] quads = new int[9];
    private static int[] numberMasks = new int[] {0, 1, 2, 4, 8, 16, 32, 64, 128, 256};
    
	public static void main(String[] args) throws Exception {
		start[0][0] = 5;
		start[1][0] = 3;
		start[0][1] = 6;
		start[1][2] = 9;
		start[2][2] = 8;
		start[4][0] = 7;
		start[3][1] = 1;
		start[4][1] = 9;
		start[5][1] = 5;
		start[7][2] = 6;
		start[0][3] = 8;
		start[0][4] = 4;
		start[0][5] = 7;
		start[1][6] = 6;
		
		start[4][3] = 6;
		start[3][4] = 8;
		start[5][4] = 3;
		start[4][5] = 2;
		start[8][3] = 3;
		start[8][4] = 1;
		start[8][5] = 6;
		start[3][7] = 4;
		start[4][7] = 1;
		start[5][7] = 9;
		start[4][8] = 8;

		start[6][6] = 2;
		start[7][6] = 8;
		start[8][7] = 5;
		start[7][8] = 7;
		start[8][8] = 9;
		
		findSolution(start, 0, 0);
		for (int i = 0;i < 9;i++) {
			for (int j = 0;j < 9;j++) {
				System.out.print(start[j][i]);
				System.out.print(" ");
			}
			System.out.println();
		}
	}
	
	private static void set(byte[][] sudoku, int positionX, int positionY, byte value) {
		int mask = numberMasks[value];
		sudoku[positionX][positionY] = value;
		rows[positionY] |= mask;
		cols[positionX] |= mask;
		quads[(positionX / 3) + (positionY / 3) * 3] |= mask;
	}

	private static void reset(byte[][] sudoku, int positionX, int positionY) {
		byte value = sudoku[positionX][positionY];
		int mask = numberMasks[value];
		sudoku[positionX][positionY] = 0;
		rows[positionY] ^= mask;
		cols[positionX] ^= mask;
		quads[(positionX / 3) + (positionY / 3) * 3] ^= mask;
	}
	
	private static int getPossibleNumbers(byte[][] sudoku, int positionX, int positionY) {
		return ~(rows[positionY] | cols[positionX] | quads[(positionX / 3) + (positionY / 3) * 3]);
	}

	
	private static boolean findSolution(byte[][] sudoku, int positionX, int positionY) {
		int possibleNumbers = getPossibleNumbers(sudoku, positionX, positionY);
		if (possibleNumbers == 0) return false;
		for(byte value = 1; value <= 9;value++) {
			if ((possibleNumbers & numberMasks[value]) != 0) {
				set(sudoku, positionX, positionY, value);
				if (positionY == 8) {
					if (positionX == 8 || findSolution(sudoku, positionX + 1, 0)) {
						return true;
					} else {
						reset(sudoku, positionX, positionY);
					}
				} else {
					if (findSolution(sudoku, positionX, positionY +1)) {
						return true;
					} else {
						reset(sudoku, positionX, positionY);
					}
				}
			}
		}
		return false;
	}
}


Evo tole sm spacal, bruteforcne random sudoku z neta takoj (nisem meril je blo pa pod sekundo). Nism pa preveru ce je resitev prov, zgleda na prvi uc.
Vse kar sm rabu narest je proper backtracking, ko resitev vec ni mozna.

Yacked2 ::

Bom z rekurzijo rešil.

Spura: hwala za pomoč, a z kopiranjem se razen CTRL+C,V ne bom ničesar naučil. Hwala za pomoč.
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

Spura ::

Itak sm zajebu. Popravek:

public class Test {
	
    private static byte[][] start = new byte[9][9];
    private static int[] rows = new int[9];
    private static int[] cols = new int[9];
    private static int[] quads = new int[9];
    private static int[] numberMasks = new int[] {0, 1, 2, 4, 8, 16, 32, 64, 128, 256};
    
	public static void main(String[] args) throws Exception {
		start[0][0] = 5;
		start[1][0] = 3;
		start[0][1] = 6;
		start[1][2] = 9;
		start[2][2] = 8;
		start[4][0] = 7;
		start[3][1] = 1;
		start[4][1] = 9;
		start[5][1] = 5;
		start[7][2] = 6;
		start[0][3] = 8;
		start[0][4] = 4;
		start[0][5] = 7;
		start[1][6] = 6;
		
		start[4][3] = 6;
		start[3][4] = 8;
		start[5][4] = 3;
		start[4][5] = 2;
		start[8][3] = 3;
		start[8][4] = 1;
		start[8][5] = 6;
		start[3][7] = 4;
		start[4][7] = 1;
		start[5][7] = 9;
		start[4][8] = 8;

		start[6][6] = 2;
		start[7][6] = 8;
		start[8][7] = 5;
		start[7][8] = 7;
		start[8][8] = 9;
		
		byte[][] solution = findSolution(start);
		for (int i = 0;i < 9;i++) {
			for (int j = 0;j < 9;j++) {
				System.out.print(solution[j][i]);
				System.out.print(" ");
			}
			System.out.println();
		}
	}
	
	private static void set(byte[][] sudoku, int positionX, int positionY, byte value) {
		int mask = numberMasks[value];
		sudoku[positionX][positionY] = value;
		rows[positionY] |= mask;
		cols[positionX] |= mask;
		quads[(positionX / 3) + (positionY / 3) * 3] |= mask;
	}

	private static void reset(byte[][] sudoku, int positionX, int positionY) {
		byte value = sudoku[positionX][positionY];
		int mask = numberMasks[value];
		sudoku[positionX][positionY] = 0;
		rows[positionY] ^= mask;
		cols[positionX] ^= mask;
		quads[(positionX / 3) + (positionY / 3) * 3] ^= mask;
	}
	
	private static int getPossibleNumbers(byte[][] sudoku, int positionX, int positionY) {
		return ~(rows[positionY] | cols[positionX] | quads[(positionX / 3) + (positionY / 3) * 3]);
	}

	
	private static byte[][] findSolution(byte[][] start) {
		byte[][] sudoku = new byte[9][9];
		for (int i = 0;i < 9;i++) {
			for (int j = 0;j < 9;j++) {
				if (start[i][j] != 0) {
					set(sudoku, i, j, start[i][j]);
				}
			}
		}
		if (findSolution(start, sudoku, 0, 0)) {
			return sudoku;
		} else {
			return null;
		}
	}
	
	private static boolean findSolution(byte[][] start, byte[][] sudoku, int positionX, int positionY) {
		int possibleNumbers = 0;
		if (start[positionX][positionY] == 0) {
			possibleNumbers = getPossibleNumbers(sudoku, positionX, positionY);
			if (possibleNumbers == 0) return false;
		} else {
			possibleNumbers = numberMasks[start[positionX][positionY]];
		}
		for(byte value = 1; value <= 9;value++) {
			if ((possibleNumbers & numberMasks[value]) != 0) {
				set(sudoku, positionX, positionY, value);
				if (positionY == 8) {
					if (positionX == 8 || findSolution(start, sudoku, positionX + 1, 0)) {
						return true;
					} else if (start[positionX][positionY] == 0) {
						reset(sudoku, positionX, positionY);
					}
				} else {
					if (findSolution(start, sudoku, positionX, positionY +1)) {
						return true;
					} else if (start[positionX][positionY] == 0) {
						reset(sudoku, positionX, positionY);
					}
				}
			}
		}
		return false;
	}
}

technolog ::

Jst sm dolga leta nazaj delal za maturitetno nalogo pri informatiki reševalec in generator sudokujev. Spodaj prilagam del za reševanje. Njegova naloga je, da poišče vse rešitve danega sudokuja (ker jih je lahko tud več). Ma pa to optimizacijo, da veji rekurzijo na polju z najmanj kandidati.

Po spominu je en sudoku rešil v povprečju v desetinki sekunde.

struct sudoku {
	vector< vector<int> > grid;
	int remaining;
	void init() {
		remaining=81;
		grid.assign(9, vector<int>(9, 0));	
	}
	sudoku() {
		init();
	}
};

// sem bo program dodal vse rešitve, ponavadi je ena
vector<sudoku> resitve;

vector<int> kandidati(sudoku &a, int x, int y) {
	//če je polje polno, kandidatov ni
	if (a.grid[x][y]!=0) {
		return vector<int>();
	}
	
	//iz polja prečrtaj vse številke, ki so že:
	vector<bool> arr(10, true);
	for (int i=0; i<9; ++i) {
		arr[a.grid[x][i]]=false; //vodoravno
		arr[a.grid[i][y]]=false; //navpično
	}
	for (int i=x/3*3; i<x/3*3+3; ++i) {
		for (int j=y/3*3; j<y/3*3+3; ++j) {
			arr[a.grid[i][j]]=false; //v 3x3 kvadratku
		}
	}
	
	vector<int> ret;
	for (int i=1; i<10; ++i) {
		if (arr[i]) {
			ret.push_back(i);
		}
	}
	return ret;
}

void solve_rec(sudoku &a) {
	if (a.remaining>0) {
		int best=10;
		pair<int, int> best_loc(0, 0);
		
		for (int i=0; i<9; ++i) {
			for (int j=0; j<9; ++j) {
				int tmp=kandidati(a, i, j).size();
				if (tmp!=0 && tmp<best) {
					best=tmp;
					best_loc=make_pair(i, j);
				}
			}
		}
		
		int x=best_loc.first, y=best_loc.second;
		vector<int> tmp=kandidati(a, x, y);
		
		for (int i=0; i<int(tmp.size()); ++i) {
			a.grid[x][y]=tmp[i];
			a.remaining--;
			solve_rec(a);
			a.remaining++;
			a.grid[x][y]=0;
		}
	} else {
		resitve.push_back(a);
	}
}

void solve(sudoku &a) {
	resitve.clear();
	solve_rec(a);
}

Zgodovina sprememb…

Spura ::

technolog je izjavil:

Ma pa to optimizacijo, da veji rekurzijo na polju z najmanj kandidati.

Mja... jst sm skepticen do takih optimizacij dokler ne izmerim ali res delujejo hitreje, sm se ze opeku v preteklosti. Take stvari sicer znajo na papirju zledat, kot da zmanjsajo stevilo korakov, v praksi pa pogosto pomenijo dodatne podatkovne strukture, dodatne cache misse, vecajo footprint algoritma v predpomnilniku itd... tale moja dost butasta java koda resi v 1.4 milisekund enga (pac JVM), ce jih pa milijon zavrtim, da se HotSpot in JIT uporabi pol je pa 60 mikro sekund en v povprecju.

technolog ::

Ta tvoja fora, da izbereš kandidate z bitnimi operacijami je kr pametna, ampak sm do nje skeptičen, ker maš zarad nje več dela pr dodajanju / odvzemanju številke.

Spura ::

Pri dodajanju, preizkusanju variant in pol backtrackanju moras vedno neki prckat. To, da flipnem 1 bit na row arrayu, col arrayu in quad arrayu se mi zdi se najhitreje. Edino kar ni ravno idealno je to, da imam kandidate kot flage in pol moram z vsemi maskami probat da najdem katere stevilke so na voljo, ampak v koncni fazi to comp en int drzi v registru pa 9 krat naredi AND operacijo in conditional branch (ker primerjam z 0 dodaten CMP ukaz ni potreben). Edin kar bi blo hitreje, ce bi slucajno lahko uporabil un strojni ukaz k mi najde prvi setiran bit z leve. Ena optimizacija k dela je to, da sm racunanje stevilke quada premaknil iz set in reset funkcij in zadeva se je pohitrila za 15-20%, zdej rabi 56 us. Fora je tut v tem, da lahko te arraye kot so quad, rows, cols komot spravis v en L1 cacheline, ce se igras pa z vektorji intov in podobno je pa prec drugo.

technolog ::

To vse bi držalo v primeru, če bi pisal assembler ali pogojno C.

Za jvm pozabi.

Spura ::

Kaj a java pa nima na konc strojne kode in ne uporablja CPU cacheov in stevilo indirekcij nima vpliva? Garantiram ti, da ga se kako ima.

napsy ::

technolog je izjavil:

To vse bi držalo v primeru, če bi pisal assembler ali pogojno C.

Za jvm pozabi.

Kokr vem JVM dolocene zadeve precej hitreje izvaja kakor ekvivalentna C/asm koda ...
"If you die, you die. But when you live you live. There is no time to waste."

Senitel ::

napsy je izjavil:

Kokr vem JVM dolocene zadeve precej hitreje izvaja kakor ekvivalentna C/asm koda ...

Good one. :)
Sure, lahko C/asm kodo napišeš tako, da bo počasna... Ampak jo lahko tudi v javi.

technolog ::

Če izvedeš C/C++ kompilacijo skupaj s profilirnimi podatki dobiš best of both worlds.

napsy ::

Senitel je izjavil:

napsy je izjavil:

Kokr vem JVM dolocene zadeve precej hitreje izvaja kakor ekvivalentna C/asm koda ...

Good one. :)
Sure, lahko C/asm kodo napišeš tako, da bo počasna... Ampak jo lahko tudi v javi.

Aja, pa pozabmo na runtime optimizacije ...
"If you die, you die. But when you live you live. There is no time to waste."

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

program, ki ti najde vse kombinacije črk oz. številk, ki mu jih podaš (strani: 1 2 )

Oddelek: Programiranje		7041832 (6524) XyNOBvxWVJ
»

[C#] Domača naloga - osnove

Oddelek: Programiranje		372498 (1715) 11tomi12
»

Kalkulator

Oddelek: Programiranje		111315 (1082) lebdim
»

[JAVA] String problem!

Oddelek: Programiranje		151665 (1362) Sergio
»

[JAVA] help

Oddelek: Programiranje		141638 (1352) keworkian

Več podobnih tem