[php]Suma liczb bez powtórzeń Opcje

[colachips]

Witam,

Chciałbym dodać do siebie kilka liczb we wszystkich możliwych kombinacjach, ale żeby działania się nie powtarzały.. Pokaże kod jaki zrobiłem

[PHP] pobierz, plaintext 
 
$liczby = $_POST['liczby'];
 
        for ($i = 1; $i <= count($liczby); $i++) {
            for ($j = 1; $j <= count($liczby); $j++) {
                echo 'Liczba '.$liczby[$i].' + Liczba '.$liczby[$j].' = '.($liczby[$i]+$liczby[$j]).'<br />';
            }
        }
 
[PHP] pobierz, plaintext 

Problem w tym, że powtarza działania, czyli np.

$liczby[1] = 111;
$liczby[2] = 222;
$liczby[3] = 333;

W wyniku tego petla wyświetli:

Liczba 111 + Liczba 111 = 222 //ok
Liczba 111 + Liczba 222 = 333 //ok
Liczba 111 + Liczba 333 = 444 //ok
Liczba 222 + Liczba 111 = 333 //blad, ta kombinacja juz byla

Będę wdzieczny za naprowadzenie na właściwy trop

[flashdev]

takie coś:

[PHP] pobierz, plaintext 
$liczby = array(1, 2, 3, 4);
 
for ($i = 0; $i < count($liczby); $i++) {
	for ($j = $i+1; $j < count($liczby); $j++) {
		echo 'Liczba '.$liczby[$i].' + Liczba '.$liczby[$j].' = '.($liczby[$i]+$liczby[$j]).'<br />';
	}
}
[PHP] pobierz, plaintext 

Edit:
Widzę, że akceptujesz też 1+1
a wiec takie coś:

[PHP] pobierz, plaintext 
$liczby = array(1, 2, 3, 4);
 
for ($i = 0; $i < count($liczby); $i++) {
	for ($j = $i; $j < count($liczby); $j++) {
		echo 'Liczba '.$liczby[$i].' + Liczba '.$liczby[$j].' = '.($liczby[$i]+$liczby[$j]).'<br />';
	}
}
[PHP] pobierz, plaintext 

Ten post edytował flashdev 10.09.2009, 19:21:15

[wookieb]

Kiedyś to robiłem i działało to mniej więcej tak

[PHP] pobierz, plaintext 
$tab = range(1,10);
$ile = count($tab);
 
for($i=0; $i<$ile; $i++)
{
    for($j = $i; $j<$ile; $j++)
    {
        echo $tab[$i].' + '.$tab[$j].' = '.($tab[$i]+$tab[$j])."\n";
    }
}
[PHP] pobierz, plaintext 

[colachips]

u ~flashdev petla nie doda np. liczby[1] do liczby[1]
u ~wookieb doda
Obydwa przykłady pomogły. Dzięki!

// edit

Ok, wszystko było fajnie do momentu gdy chciałem rozszerzyć funkcjonalność tego skryptu aby wyświetlał faktycznie wszystkie kombinacje sum. Rozważmy przykład:

[PHP] pobierz, plaintext 
$liczby = array(1, 2, 3, 4);
 
        for ($i = 1; $i <= count($liczby); $i++) {
            for ($j = $i + 1; $j <= count($liczby); $j++) {
                $suma = $liczby[$i] + $liczby[$j];
                if (($suma % 1000) == 0) {
                    $suma = '<span style="color: red">'.$suma.'</span>';
                }
                echo $liczby[$i].' + '.$liczby[$j].' = '.$suma.'<br />';
                for ($k = $j + 1; $k <= count($liczby); $k++) {
                    $suma = $liczby[$i] + $liczby[$j] + $liczby[$k];
                    if (($suma % 1000) == 0) {
                        $suma = '<span style="color: red">'.$suma.'</span>';
                    }
                    echo $liczby[$i].' + '.$liczby[$j].' + '.$liczby[$k].' = '.$suma.'<br />';
                }
            }
        }
[PHP] pobierz, plaintext 

W wyniku pokaże się:

1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 4 = 7
1 + 3 = 4
1 + 3 + 4 = 8
1 + 4 = 5
2 + 3 = 5
2 + 3 + 4 = 9
2 + 4 = 6
3 + 4 = 7

Czyli brakuje kombinacji 1 + 2 + 3 + 4 = 10

A co jeśliby było 10 liczb? 10 pętli for? Musi być prostsze rozwiązanie..

Ten post edytował colachips 10.09.2009, 22:15:51

[wookieb]

Nie. Musisz zauważyć pewne zależności przy kolejnych kombinacjach i odpowiednio je zrealizować. Ale powiedz do czego ci to potrzebne?
Nie wiem czy wyszło mi dobrze ale sprawdź

[PHP] pobierz, plaintext 
$tab = range(1,6);
$ile = count($tab);
 
$firstNumber = 0;
$results = array();
 
while($firstNumber < $ile)
{
	$rangeBegin = $firstNumber+1;
	$rangeEnd = $rangeBegin; // $firstNumber+1 :)
 
	$results[] = $tab[$firstNumber].' + '.$tab[$firstNumber].' = '.($tab[$firstNumber]*2);
	while( !($rangeBegin==$rangeEnd && $rangeEnd == $ile) )
	{
		//zakres dodawanych liczb
		$rangeStr = '';
		$rangeSum = 0;
		for($i=$rangeBegin; $i<$rangeEnd; $i++)
		{
			$rangeStr .= ' + '.$tab[$i];
			$rangeSum += $tab[$i];
		}
 
		// no i wynik
		for($c = $rangeEnd; $c<$ile ; $c++)
		{
			$results[] = $tab[$firstNumber].$rangeStr.' + '.$tab[$c].' = '.($tab[$firstNumber] + $tab[$c] + $rangeSum);
		}
 
		// zmieniamy zakresy liczb dodawanych
		$rangeEnd++;
		if($rangeEnd >= $ile)
		{
			$rangeBegin++;
			if($rangeBegin >= $ile) break;
 
			$rangeEnd = $rangeBegin + 1;
		}
	}
 
	$firstNumber++;
}
 
print_r($results);
[PHP] pobierz, plaintext 

Jeżeli coś nie pasuje to masz solidny początek, który możesz sobie zmodyfikować.

Ten post edytował wookieb 11.09.2009, 09:41:43

[flashdev]

proszę:

[PHP] pobierz, plaintext 
$liczby = array(1, 2, 3, 4, 5, 6);
$count = count($liczby);
$vector = array();
$res = array();
for ($i = 0; $i < pow($count+1, $count); $i++) {
	$vector[0] = $i%($count+1);
	for( $j = 1; $j < $count; $j++ ){
		$vector[$j] = ($i - $vector[$j-1])/(pow(($count+1), $j))%($count+1);
	}
	$str = mkStr($vector, $liczby);
	if( !empty($str) ){
		$res[$i] = $str;
	}
	//echo $vector[0] . ' ' . $vector[1] . ' ' . $vector[2] . ' ' . $vector[3] . '<br />';
}
 
echo '<pre>';
var_dump(array_unique($res));
echo '</pre>';
 
function mkStr(&$v, &$l){
	$count = count($v);
	$arr = array();
	$cnt = 0;
	for( $i = 0; $i < $count; $i++ ){
		if( $v[$i] != $count ){
			$arr[$cnt] = $l[$v[$i]];
			$cnt++;
		}
	}
	if( count($arr) > 1 ){
		sort($arr);
		return implode(' + ', $arr);
	}
	return '';
}
[PHP] pobierz, plaintext 

Rozwiązanie nie jest zbyt dobrze napisane (bardzo obciąża komputer), ale jest najprostsze w implementacji jakie udało mi się wymyślić.
Prawdopodobnie jest to najgorsza z możliwych implementacji, ale za tą lepszą trzeba zapłacić
Jedyna zaleta tego rozwiązania jest taka, że spełnia założenia.

@wookieb Twoje rozwiązanie zwraca 56 wyników dla 6 liczb, więc chyba zapomniałeś o "kilku"
Zwróć uwagę na ogranicznik mojej pętli

[PHP] pobierz, plaintext 
$i < pow($count+1, $count)
[PHP] pobierz, plaintext 

Tak, niestety jest to zależność potęgowa (x^x).

[wookieb]

Wiem, ale dałem mu taką podstawę z której będzie mógł kombinować resztę.

// EDIT Ponieważ miałem sporo błędów to postanowiłem, zrobić to zupełnie inaczej.

[PHP] pobierz, plaintext 
// Skrypt tworzy możliwe kombinacje dodawania liczb. (bez powtarzania liczby w działaniu) metoda bitowa
// np
/*
 1 + 2 = 3
 1 + 3 = 4
 1 + 4 = 5
 1 + 2 + 3 = 6
 1 + 2 + 4 = 7
 itd
*/
$tab = range(1,10);
$ile = count($tab);
 
$num = str_repeat('1', $ile);
$num = bindec($num); // mamy (prawie) wyliczoną liczbę możliwych kombinacji
 
$tmpNum = $num;
$results = array();
 
while($tmpNum > 0)
{
	// zeby errorow nie bylo
	$tmpNumStr = str_pad(decbin($tmpNum), $ile, '0', STR_PAD_LEFT);
 
	$sum = 0;
	$sumStr = '';
	$numsAdded = 0;
 
	for($i=0; $i<$ile; $i++)
	{
		// czy wstawic liczbe
		if($tmpNumStr[$i] == '1')
		{
			$sum+= $tab[$i];
			$sumStr.=' + '.$tab[$i];
			$numsAdded++;
		}
	}
	// jezeli tylko jedna liczba to nie jest to działanie
	if($numsAdded>1)
	{
		$results[] = substr($sumStr, 3).' = '.$sum;
	}
 
	$tmpNum --;
}
print_r($results);
[PHP] pobierz, plaintext 

Ten post edytował wookieb 11.09.2009, 12:04:10

[colachips]

Imponujące! Muszę jeszcze zrozumieć JAK to wszystko działa.. Kiedy pojmę to dam znać. Dzieki za pomoc!

[wookieb]

Zapis bitowy ( dwójkowy) liczby pokazuje nam jakie liczby mamy wziąć do działania.
W zapisie bitowym liczby wyglądają np tak
1) 0001
2) 0010
3) 0011
4) 0100
5) 0101
6) 0110
7) 0111
...
Mamy teraz twoje liczby 1,2,3,4. Podstawmy twoje liczby na odpowiednie pozycje. Z pozycji gdzie jest 1 pobieramy odpowiadającą jej (pozycji) liczbę i wstawiamy do działania. Jeżeli w całym ciągu, jest tylko jedna 1 to olewamy

Przykład:

Kod

      1 | 2 | 3 | 4  | wynik
     -----------------
1)  - 0 | 0 | 0 | 1  | ------
2)  - 0 | 0 | 1 | 0  | ------
3)  - 0 | 0 | 1 | 1  | 3 + 4 = 7
4)  - 0 | 1 | 0 | 0  | ------
5)  - 0 | 1 | 0 | 1  | 2 + 4 = 6
6)  - 0 | 1 | 1 | 0  | 2 + 3 = 5
7)  - 0 | 1 | 1 | 1  | 2 + 3 + 4 = 9
8)  - 1 | 0 | 0 | 0  | ------
9)  - 1 | 0 | 0 | 1  | 1 + 4 = 5
10) - 1 | 0 | 1 | 0  | 1 + 3 = 4
11) - 1 | 0 | 1 | 1  | 1 + 3 + 4 = 8
12) - 1 | 1 | 0 | 0  | 1 + 2 = 3
13) - 1 | 1 | 0 | 1  | 1 + 2 + 4 = 7
14) - 1 | 1 | 1 | 0  | 1 + 2 + 3 = 6
15) - 1 | 1 | 1 | 1  | 1 + 2 + 3 + 4 = 10 (dlatego na początku wstawiłem same 1 do ciągu i przeliczyłem na system dziesięty, przez co otrzymałem liczbę potrzebnych operacji. od tej wartości odejmiemy ilość liczb jakie mamy i otrzymujemy liczbę możliwych kombinacji (u nas 15 - 4 = 11) )

Ten post edytował wookieb 11.09.2009, 13:14:02

[flashdev]

Zapis bitowy ( dwójkowy) liczby pokazuje nam jakie liczby mamy wziąć do działania.
W zapisie bitowym liczby wyglądają np tak
1) 0001
2) 0010
3) 0011
4) 0100
5) 0101
6) 0110
7) 0111
...

Pomijasz jeden mały szczegół:

u ~flashdev petla nie doda np. liczby[1] do liczby[1]
u ~wookieb doda
Obydwa przykłady pomogły. Dzięki!

[wookieb]

A co za problem zrobić to poza pętlą? Albo nawet w niej

Kod

if($numsAdded>1)
{

}
else
{
// dodaj te same liczby
}

Z przykładu nie wynikało, że chciał takie działanie, więc może zmienił zdanie.

Ten post edytował wookieb 11.09.2009, 13:31:56

[flashdev]

A co za problem zrobić to poza pętlą? Albo nawet w niej

Kod

if($numsAdded>1)
{

}
else
{
// dodaj te same liczby
}

Z przykładu nie wynikało, że chciał takie działanie, więc może zmienił zdanie.

Jakie to proste

A jak z tablicy 1, 2, 3 zrobisz:
1 + 1 + 2?

[wookieb]

Nie wiem czy zauwazyłeś ale z przykładu autor nie brał takiej kombinacji pod uwagę.. Ani nawet 1 + 1.

Ten post edytował wookieb 11.09.2009, 13:40:30