CODEWITHSUNDEEP
c++arraysalgorithm
MatKravi
MatKravi

Reputation: 43

Make position hierarchy in array

I have the following task. We get a number N - size and an array filled with integers in a way to work for this algorithm. Now every number in our array is basically a position in the array. Every array has a leader. It's the point that has the same value as it's position in array. An example array would be:

1 2 4 5 4 1

In this array the leader is value 4 because it's on the 4th position. In the data we get there must always be one leader. Now we make a hierarchy. The leader gets the value 0, the ones that point at him, so have the value of 4 in this case get the new value 1 and so on. To visualize it, the array above becomes:

3 2 1 4 0 3

Leader is 0, at position 2 we had a 4 as well so it became the next one in hierarchy with number 1. At position 1 we had a 2 so it was pointing at the 2nd position - the new 1 in hierarchy so it becomes the 2nd in hierarchy and so on. Every other 2 in original array would become a 2 as well.

The input data will be given as txt file. For now I need the best algorithm to do the job. I made one using recursion. Here i also want to ask what the complexity is. Is it N*logN?The input comes from a file, so does N. Example input file.txt is
4
1 2 3 3
6
1 2 4 5 4 1

Output for above(later):
3 2 1 0
3 2 1 4 0 3

Here's my code(input fixed for now):

#include <iostream>
using namespace std;

int *T;

int nr(int x)
{
if (T[x] == x)
    return 0;
else
    return nr(T[x]) + 1;
}

int main()
{
    int n, m, leader;

    n = 6;
    T = new int[n];
    int T1[6];

    T[0] = 1;
    T[1] = 2;
    T[2] = 4;
    T[3] = 5;
    T[4] = 4;
    T[5] = 1;

    for (int i = 0; i < n; ++i)
    {   
        T1[i] = nr(i);  
    }

    for (int i = 0; i < n; ++i)
    {
        cout<<T1[i]<<" ";
    }
    cout << endl;

    delete[] T;
}

Upvotes: 2

Views: 153

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

For each position, we'd like to know which cells are pointing to it.

1 2 4 5 4 1

5: 3
4: 2, 4 (leader)
3: None
2: 1
1: 0, 5
0: None

Now follow backwards from the leader:

Who's looking at 4?
  -> 2
[x, x, 1, x, 0, x]

Who's looking at 2?
  -> 1
[x, 2, 1, x, 0, x]

Who's looking at 1?
  -> 0 and 5
[3, 2, 1, x, 0, 3]

Who's looking at 0 or 5?
  -> 3
[3, 2, 1, 4, 0, 3]

Pseudocode:

// For each position, we'd like to know
// which cells are pointing to it
A = input array
leader = None
map = {}

for i=0 to length(A)-1:
  if i = A[i]:
    leader = i

  if i != leader:
    if A[i] in map:
      map[A[i]].append(i)
    else:
      map[A[i]] = [i]


//Now follow backwards from the leader
output = Array(length(A))
next = leader
output[leader] = 0
rank = 0

// Assumes the data provides
// for a straightforward solution.
// There may be edge cases to work
// out if that's not the case.
while next:
  for i in map[next]:
    next = None
    if i in map:
      next = i
      rank = rank + 1
      for j in map[next]:
        output[j] = rank
      break

Upvotes: 2

Related Questions