Forum » Programiranje » [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
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:
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
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.
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:
Na sudoku se bom z bruteforcom spravil :)
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 ::
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!
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 :)
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č.
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.
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…
- spremenil: technolog ()
Spura ::
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.
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 ::
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 ::
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 ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | program, ki ti najde vse kombinacije črk oz. številk, ki mu jih podaš (strani: 1 2 )Oddelek: Programiranje | 41856 (6548) | XyNOBvxWVJ |
| » | [C#] Domača naloga - osnoveOddelek: Programiranje | 2498 (1715) | 11tomi12 |
| » | KalkulatorOddelek: Programiranje | 1316 (1083) | lebdim |
| » | [JAVA] String problem!Oddelek: Programiranje | 1668 (1365) | Sergio |
| » | [JAVA] helpOddelek: Programiranje | 1640 (1354) | keworkian |