Pärchen ordnen

CDW

0
Mitarbeiter
Also, man hat mehrere Zahlenpärchen: 1 1 2 2 3 3 4 4
diese sollte man so anordnen, dass jede Zahl immer auch den Abstand zu ihrem Partner angibt. Bsp für 1 1 2 2 3 3 4 4
[2,3,2,4,3,1,1,4] ?
[1,1,3,4,2,3,2,4] ? ;
[3,4,2,3,2,4,1,1] ? ;

Schreibe also ein Programm, welches eingegebene Zahlenpärchen in eine gültige Kombination anordnet und gebe eine mögliche Lösung für 1 1 2 2 3 3 4 4 5 5 an:
Lösung 1: [1,1,3,4,5,3,2,4,2,5]
(es gibt noch 9 weitere ;) )
 
Hier mal mein Ansatz (gibt nur eine Lösung aus. sobald ich Zeit dazu habe werde ich das mal verbessern)
Bin das ganze mal nach dem Trial and Error Prinzip angegangen:
Code:
#include <stdio.h>

int next(int);
int buf[10]={0,0,0,0,0,0,0,0,0,0};

int main()
{
	int i;
	next(1);
	
	for(i=0;i<10;i++)
		printf("%d", buf[i]);
	printf("\n");
	return 0;
}

int next(int n)
{
	int p;
	if(n>5)
		return 1;
	for(p=0;p<10;p++)
	{
		if(p+n>=10)
			return 0;
		if(buf[p]==0&&buf[p+n]==0)
		{
			buf[p]=buf[p+n]=n;
			if(next(n+1))
				return 1;
			else
				buf[p]=buf[p+n]=0;
		}
	}
	return 0;
}
1152423543 spuckt mir das Programm als Lösung aus.

mfg, loose
 
Mein Code:
Code:
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n[] = {1, 2, 3, 4, 5};
    const int countPairs = 5;
    const int countDigits = 2*countPairs;
    int *a = new int[countDigits];

    for (int i = 0; i < countPairs; i++)
        a[i] = 0;

    do {
        int iAdd = 0;
        for (int i = 0; i < countPairs; i++) {
            while (a[i + iAdd] != 0 && i + iAdd < countDigits)
                iAdd += 1;
            if (i + iAdd >= countDigits || i + iAdd + n[i] >= countDigits)
                break;
            a[i + iAdd] = n[i];
            a[i + iAdd + n[i]] = n[i];
        }
        bool isResult = true;
        for (int i = countPairs; i < countDigits; i++) {
            if (a[i] == 0) {
                isResult = false;
                break;
            }
        }
        if (isResult) {
            for (int i = 0; i < countDigits; i++) {
                cout << a[i] << " ";
            }
            cout << endl;
        }
        for (int i = 0; i < countDigits; i++)
            a[i] = 0;
    } while (next_permutation(n, n+countPairs));
}

Ich komme aber bei weitem nicht auf 159 Möglichkeiten. Mein Code generiert folgende:
1 1 3 4 5 3 2 4 2 5
1 1 5 2 4 2 3 5 4 3
2 3 2 5 3 4 1 1 5 4
2 4 2 3 5 4 3 1 1 5
3 4 5 3 2 4 2 5 1 1
3 5 2 3 2 4 5 1 1 4
4 1 1 5 4 2 3 2 5 3
4 5 1 1 4 3 5 2 3 2
5 1 1 3 4 5 3 2 4 2
5 2 4 2 3 5 4 3 1 1
Welche fehlen mir denn da?
 
Ich komme aber bei weitem nicht auf 159 Möglichkeiten.
War ein bisschen voreilig von mir (habe die Spiegelungsmöglichkeiten falsch gezählt bzw mir nur die Anzahl der Lösungen ausgeben lassen).
Korrekterweise sind es nur natürlich nur 10.
[[1,1,3,4,5,3,2,4,2,5],
[1,1,5,2,4,2,3,5,4,3],
[2,3,2,5,3,4,1,1,5,4],
[2,4,2,3,5,4,3,1,1,5],
[3,4,5,3,2,4,2,5,1,1],
[3,5,2,3,2,4,5,1,1,4],
[4,1,1,5,4,2,3,2,5,3],
[4,5,1,1,4,3,5,2,3,2],
[5,1,1,3,4,5,3,2,4,2],
[5,2,4,2,3,5,4,3,1,1]]
 
so ich hab mir auch noch ne Lsg. einfallen lassen in C welche Rekursion benutzt:
(als Parameter wird die höchste Ziffer in der Liste angegeben)

Code:
#include <stdio.h>
#include <stdlib.h>

void print_array(int array[], int size)
{
  int i;
  for(i=0; i<size; i++) printf("%d ", array[i]);
  printf("n");
}

void place(int num, int array[], int size)
{
  int i;
  if(num==0) print_array(array, size);
  else
  {
    for(i=0; i<size-num; i++)
    {
      if(array[i]==0 && array[i+num]==0)
      {
        array[i]=num;
        array[i+num]=num;
        place(num-1, array, size);
        array[i]=0;
        array[i+num]=0;
      }
    }
  }
return;
}

int main(int argc, char *argv[])
{
  if(argc!=2) printf("Argument Errorn");
  int size, i, array[];

  size=atoi(argv[1]);
  array=malloc(size*2);
  for(i=0; i<size*2; i++) array[i]=0;

  place(size, array, size*2);

  return 0;
}

MfG mYstar
 
Python
Code:
from itertools import permutations

def valid(ps):
    def f(x):
        return ps.index(x)+x < len(ps) and ps[ps.index(x)+x] == x
    return all(map(f, range(1, len(ps)/2+1)))

def solve(xs):
    return set(filter(valid,permutations(xs)))

solutions = solve([1,1,2,2,3,3,4,4,5,5])
for sol in solutions: print " ".join(map(str, sol))
print ">> %i" % len(solutions)
Gruß
Felix
 
Zurück
Oben