Sprawdzenie czy elementy nie na chodzą na siebie

0

Cześć Mam takie pytanie. Jak sprawdzić czy elementy w liscie nie na chodzą na siebie ?
że wszystkie elementy są jakby jednostajne i nie na chodzą na siebie

    public class Entity
    {
        public int Start { get; set; }
        public int End { get; set; }

        public Entity(int start, int end)
        {
            this.Start = start;
            this.End = end;
        }
    }
    class Program
    {

        static void Main(string[] args)
        {
            List<Entity> list = new List<Entity>()
            {
                new Entity(1,2),
                new Entity(3,4),
                new Entity(5,6)
            }; //Tutaj jest ok jest zachowany ciąg 
            
                        List<Entity> list = new List<Entity>()
            {
                new Entity(1,3),
                new Entity(2,4)
            }; //Tutaj jest nie ok bo drugi element start jest mniejszy niż 3
        }
    }

Jak stworzyć metodę która by zwracała true false

0

Czy Entity(1,2) nachodzi na Entity(2,3)?

1

Na temat odpowiadaj w postach :-)

Oki, to teraz: jak dużo danych wejściowych oczekujesz? Dziesiątki, tysiące, miliony?

0

Przepraszam jasne pewnie :)
Wiesz nie wiem zastanawiam się jak mogę to zrobić założy że dziesiątki :)

1
		static void Main(string[] args)
		{
			List<Entity> list = new List<Entity>()
            {
                new Entity(1,2),
                new Entity(3,4),
                new Entity(5,6)
            };

			List<Entity> list2 = new List<Entity>()
            {
                new Entity(1,3),
                new Entity(2,4)
            };

			Console.WriteLine("list1: {0}, list2: {1}", isRelative(list), isRelative(list2));
			Console.ReadKey();
		}

		public class Entity
		{
			public int Start { get; set; }
			public int End { get; set; }

			public Entity(int start, int end)
			{
				this.Start = start;
				this.End = end;
			}
		}

		public static bool isRelative(List<Entity> lst)
		{
			for(int i = lst.Count - 1; i > 0; i--)
				if(lst[i].Start - lst[i - 1].Start != 2)
					return false;
			return true;
		}

Natomiast, jeśli chcesz jedynie sprawdzić czy "różnica" jest inna to:

		public static bool isRelative(List<Entity> lst, int checkValue = 2)
		{
			int possibleRelative = 0;
			bool _c = false;

			if(lst.Count < 2)
				return false;
			else if(lst.Count == 2)
			{
				if(lst[1].Start - lst[0].Start != checkValue)
					return false;
				return true;
			}
			else
			{
				for(int i = lst.Count - 1; i > 0; i--)
				{
					int _dif = lst[i].Start - lst[i - 1].Start;
					if(!_c)
					{
						possibleRelative = _dif;
						_c = true;
						continue;
					}
					else
					{
						if(_dif != possibleRelative)
							return false;
					}
				}
			}
			return true;
		}
1

W takim razie najprościej byłoby, gdybyś w klasie Entity stworzył metodę bool doesOverlap(Entity other) i potem całość sprowadza się do (w pseudokodzie):

for first in list:
  for second in list:
    if first != second && first.does_overlap(second):
      pairs.add((first, second))

Ten algorytm ma złożoność kwadratową, stąd będzie mało praktyczny dla większego zbioru danych, ale powinien sprawdzić się w Twoim przypadku :-)

Jeśli Twój zbiór wejściowy ma jakąś ciekawą charakterystykę (np. dane są posortowane po Start), to wydaje mi się, że można by to rozwiązać nawet liniowo - z tym, że prawdopodobnie u Ciebie i tak nie ma takiej potrzeby.

2
		public static bool isRelative(List<Entity> lst, int checkStartValue = 2, int checkEndValue = 2)
		{
			int possibleRelativeStart = 0, possibleRelativeEnd = 0;
			bool _c = false;

			if(lst.Count < 2)
				return false;
			else if(lst.Count == 2)
			{
				if(lst[1].Start - lst[0].Start != checkStartValue)
					return false;
				if(lst[1].End - lst[0].End != checkEndValue)
					return false;
				return true;
			}
			else
			{
				for(int i = lst.Count - 1; i > 0; i--)
				{
					int _difStart = lst[i].Start - lst[i - 1].Start;
					int _difEnd = lst[i].End - lst[i - 1].End;
					if(!_c)
					{
						possibleRelativeStart = _difStart;
						possibleRelativeEnd = _difEnd;
						_c = true;
						continue;
					}
					else
					{
						if(_difStart != possibleRelativeStart || _difEnd != possibleRelativeEnd)
							return false;
					}
				}
			}
			return true;
		}

Specjalnie dla @Patryk27. Już lepiej? Brakuje jeszcze w Twoim komentarzu złożoności kwantowej i ciał niebieskich. Śmieszy mnie jak straszycie nowicjuszy że programowanie takie hurr durr genialne dla geniuszy.

1

Jak chcesz się pozbyć elementów nie pasujących do to można też tak:

List<Entity> list = new List<Entity>()
            {
                new Entity(1,5),
                new Entity(5,4),
                new Entity(6,8),
                new Entity(3,6),
                new Entity(9,19)
            };

             list.ToList().Aggregate((prev, next) => {
                 if (prev.End > next.Start || next.End<next.Start)
                 {
                     list.Remove(next);
                     return prev;
                 }
                return next;
            });
1

Już lepiej?

Sprawdź dla [ Entity(1,5), Entity(10,15), Entity(3,12) ] - wg mnie te dane się pokrywają (po narysowaniu na osi), choć zdaje się, że Twoja funkcja zwróci false.

Śmieszy mnie jak straszycie nowicjuszy że programowanie takie hurr durr genialne dla geniuszy.

Nie postrzegam tego w ten sposób - podałem najprostsze możliwe rozwiązanie (które personalnie uważam za czytelniejsze od Twojego) i dodatkowo rozszerzyłem temat wspominając o jego wadach oraz możliwym innym podejściu, aby OP mógł poszerzyć swoją wiedzę.

Nie widzę tutaj nic wymagającego ponadprzeciętnego IQ, podobnie jak nie dostrzegam powodu do mówienia wy - jeśli uważasz, że ja mogłem coś napisać klarowniej, powiedz i wytłumacz jak Ty to widzisz, bez niepotrzebnego sarkazmu czy ironii; wszyscy jesteśmy przecież ludźmi.

Brakuje jeszcze w Twoim komentarzu złożoności kwantowej i ciał niebieskich

Nie rozumiem dlaczego mnie atakujesz - IMO normalnie wspomniałem o tym, że Twój algorytm jest moim zdaniem błędny, wskazując na konkretny powód.

1 użytkowników online, w tym zalogowanych: 0, gości: 1