Click here to Skip to main content
15,881,898 members
Please Sign up or sign in to vote.
3.67/5 (3 votes)
See more:
Hello, i have an array something like this 1,1,2,2,1,1,2,2,1,3,3,3,3,3,4,4 and i need to count how many times a pair of elemnts at a distnace d from eachother its in that array. for example d=2, x[0]=1; x[0+d]=2; For pair 1-2 we have 4 occurence in array;
this problem is bugging my mind it must be something easy but i cant find the answer how to do it. And the array is gonna be verry big so it has to be fast also. Can you help me pls?
Posted
Updated 28-Jan-12 21:08pm
v2
Comments
Sergey Alexandrovich Kryukov 29-Jan-12 3:08am    
Homework, interview question?
--SA
Amir Mahfoozi 29-Jan-12 3:19am    
It is just two nested loops, so try to implement it and if you get errors mention it here.
aryx123 29-Jan-12 3:20am    
Its more like a project of my own. I am new in c# and i want to learn as much as possible, this part is a small part from a texture based image recognition.
aryx123 29-Jan-12 5:15am    
for one specific pair i can do it with nested loops but the problem is when i have more pairs to count
[no name] 29-Jan-12 7:12am    
Which version of C# or .NET framework are you using?

Well, this shouldn't be to difficult I think?
You start out by figuring out what your first number is, in your example 1, then you check the number at the specified index.
Now make a for loop that checks any number and if it is the same as your first number and if it is also check the current index + the specified index.
Something like this:
C#
static int GetNumberOfPairs(IEnumerable<int> arr, int distance)
{
    int counter = 0;
    // Check if your collection is big enough to begin with.
    if (arr.Count() > distance)
    {
        // Get the numbers you need.
        int firstNo = arr.ElementAt(0);
        int secondNo = arr.ElementAt(distance);
        // Loop through the collection and stop when adding
        // the index would cause an OutOfRangeException.
        for (int i = 0; i < arr.Count() - distance; i++)
        {
            // If the current index matches the first number,
            // then also check if current index + distance is the second number.
            if (arr.ElementAt(i) == firstNo && arr.ElementAt(i + distance) == secondNo)
            {
                // If it is increment a counter.
                counter++;
            }
        }
    }
    // Return the counter.
    return counter;
}
</int>

I'm not a C# programmer, so forgive me if the code looks odd...
You might need to tweak this code a bit since I haven't tested it very much. But it matched with your example.
Also, I'm not saying this is THE solution. It is A solution. There's probably others and maybe better solutions. This one is certainly (probably) easiest though :)
Hope this helps!
 
Share this answer
 
v2
Comments
aryx123 29-Jan-12 15:26pm    
thank you so much i think this will work just fine as a restarting point
Sander Rossel 29-Jan-12 15:28pm    
Glad to be of help. Don't forget to accept the answer that helped you so others will know you've been helped sufficiently too :)
aryx123 29-Jan-12 15:30pm    
sorry about that its my first post
aryx123 29-Jan-12 15:31pm    
didnt saw that big green button
Espen Harlinn 29-Jan-12 15:35pm    
My 5
Out of curiosity, I ventured into other ways of solving this problem - as mentioned by Naerling

C#
//The pattern conveys - the first digit followed by d other digits then followed by the second digit
//firstNo="1"; secondNo="2"; distance="2"; All firstNo,secondNo,distance are String.
Regex regexObj=new Regex(firstNo + @"\d{" + distance + "}" + secondNo);
//Match collection gets all occurences of this regular expression
MatchCollection MatchObj = regexObj.Matches("1122112213333344");
//Just printing the occurence count!
Console.WriteLine(MatchObj.Count);


Feels elegant, and as I've tried out, It's working as it should.

Can you try this way and let me know it's aptness for your problem?

PS: This requires System.Text.RegularExpressions library to be used.
 
Share this answer
 
v6
Comments
BillWoodruff 29-Jan-12 17:01pm    
Interesting ! I assume that you have pre-defined the variables 'firstNo, 'distance, and 'secondNo ? As you may guess, I do not use RegEx, but doubt 'firstNo is a RegEx operator (and am ready to change my opinion !).
[no name] 29-Jan-12 17:17pm    
firstNo/secondNo are both string.
BillWoodruff 29-Jan-12 17:42pm    
You mean they ARE variables you have defined in advance as strings ... yes ?

best, Bill
[no name] 29-Jan-12 17:45pm    
Yeah Bill. Both are strings. (They can be int as well, would work fine that way too)
BillWoodruff 29-Jan-12 18:36pm    
I am too ignorant of RegEx (and intend to stay that way), to know they could be either numbers or strings :)
How about:

C#
int[] arr = {2, 1, 1, 2, 2, 1, 3, 3, 3, 3, 3, 4, 4};
int d = 2;
int a = 1
int b = 2;
var e = arr.Skip(d).GetEnumerator();
int m = arr.Take(arr.Length-d).Count(v=>e.MoveNext() && v==a && e.Current==b);


Not that I would really program like this... ;-)

Cheers

Andi
 
Share this answer
 
Comments
aryx123 30-Jan-12 8:51am    
this solution works also but same it counts the pairs again when it meets second,third...etc time
Andreas Gieriet 30-Jan-12 12:17pm    
From your comment, I read that the given solution is not exactly what you are looking for.
For the given array in your example: what is the expected outcome?

Cheers

Andi
aryx123 30-Jan-12 12:41pm    
for this array{ 2, 1, 1, 2, 2, 1, 3, 3, 3, 3, 3, 4, 4} and a distance d=2 the expected outcome should be somehing like this: 2-1=2; 1-2=2; 2-3=1; 1-3=1; 3-3=3; 3-4=2;
for my array {1,1,2,2,1,1,2,2,1,3,3,3,3,3,4,4} and a distance d=1 the expected outcome should be:1-1=2; 1-2=2; 2-2=2; 1-3=1; 3-3=4; 3-4=1; 4-4=1;
aryx123 31-Jan-12 9:45am    
so any ideea?
Andreas Gieriet 31-Jan-12 10:05am    
I still don't get it. All the algorithms deliver for a specific pair/diatance the count.
Do you want for all permutations of pairs with the given distance the data?
What shall be the structure to return the data (or do you simply want to print the pairs)?
I'm still confused.

BTW: please press the "Reply" button top right of this comment to reply to this.
This is now a solution as requested in the comments of solution 3.
Speed is maybe not optimal, though...

C#
static void Main(string[] args)
{
    int[] arr = {2, 1, 1, 2, 2, 1, 3, 3, 3, 3, 3, 4, 4};
    int step = 2;

    var r = GetPermutations(arr, step);
    Console.WriteLine("arr  = {0}", string.Join(",", arr));
    Console.WriteLine("step = {0}", step);
    foreach (var e in r)
    {
        Console.WriteLine("{0}-{1} = {2}", e.Key.Item1, e.Key.Item2, e.Value);
    }

}
// returns unsorted dictionary of permutation counts of pairs step index positions appart
public static Dictionary<Tuple<int, int>, int> GetPermutations(int[] arr, int step)
{
    Dictionary<Tuple<int, int>, int> r = new Dictionary<Tuple<int, int>, int>();
    var e1 = arr.Take(arr.Length-step).GetEnumerator();
    var e2 = arr.Skip(step).GetEnumerator();
    while(e1.MoveNext() & e2.MoveNext())
    {
        Tuple<int, int> k = new Tuple<int,int>(e1.Current, e2.Current);
        if (r.ContainsKey(k)) r[k]++;
        else r.Add(k, 1);
    }
    return r;
}


Output:
arr  = 2,1,1,2,2,1,3,3,3,3,3,4,4
step = 2
2-1 = 2
1-2 = 2
2-3 = 1
1-3 = 1
3-3 = 3
3-4 = 2


Cheers

Andi

[EDIT]
...and here is the .Net2.0 Version:
Not optimal, but it works...
C#
static void Main(string[] args)
{
    int[] arr = {2, 1, 1, 2, 2, 1, 3, 3, 3, 3, 3, 4, 4};
    int step = 2;

    var r = GetPermutations(arr, step);
    Console.WriteLine("arr  = {0}", 
               string.Join(",",
                      Array.ConvertAll(arr, 
                           delegate(int i) { return i.ToString(); })));
    Console.WriteLine("step = {0}", step);
    foreach (var e in r)
    {
        Console.WriteLine("{0}-{1} = {2}", e.Key.Key, e.Key.Value, e.Value);
    }

}
// returns unsorted dictionary of permutation counts of pairs step appart
public static Dictionary<KeyValuePair<int,int>,int> GetPermutations(int[] arr, int step)
{
    Dictionary<KeyValuePair<int,int>,int> r = 
                  new Dictionary<KeyValuePair<int,int>,int>();
    var e1 = arr.GetEnumerator();
    var e2 = arr.GetEnumerator();
    while ((step > 0) && e2.MoveNext()) step--;
    while(e1.MoveNext() & e2.MoveNext())
    {
        KeyValuePair<int, int> k =
               new KeyValuePair<int, int>((int)e1.Current, (int)e2.Current);
        if (r.ContainsKey(k)) r[k]++;
        else r.Add(k, 1);
    }
    return r;
}
 
Share this answer
 
v4
Comments
aryx123 31-Jan-12 16:58pm    
i dont have .net framework 4 on my job pc but ill try it tommorow at home(on .net 3.5 i dont have Tuple). after a look on the code it has to work Thank you so much!
aryx123 1-Feb-12 5:45am    
both codes work Yeeyyyyy!!! :D thank you so much!
with respect Aryx.
Andreas Gieriet 5-Feb-12 8:18am    
You are welcome!
Cheers
Andi

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900