array duplications

[cdg]

Could anyone tell me how to write a loop for an array, that would have to
check each iteration for duplications of previous entered values. So, the
exact number of loops is not known, but the total number of array elments is
known.

Example: array size - array[100]

(some type of loop statement)
{
array[n] "equal to" or "not equal to" a variable. If not a duplication,
increase the count by one. If it is a duplication, check the next variable
for duplication and so on.
}

This is only approach I have tried, but it is not working.

while(i<100)
{
ct += 1;

"statements "

for(n=0; n<ct; n++)
{
array[n] != var.name ? array[n] == var.name : n--
}
}

[Dietmar Kuehl]

cdg wrote:

Could anyone tell me how to write a loop for an array, that would have
to check each iteration for duplications of previous entered values. So,
std::vector<T> array;
while (array size is less than 100)
{
T value;
read value;
if (not find value in array)
push value to the end of array
}

It is a pretty simple algorithm. You are doing something rather
different:
while(i<100)
Where is "i" coming from?
{
ct += 1;
The array content is always increased which is almost certainly
not what you want.
"statements "

for(n=0; n<ct; n++)
{
array[n] != var.name ? array[n] == var.name : n--

Think of it! Why would you want to assign the new value in each
iteration? Also, you need to track what the meaning of your
variables is! 'n' is just the local loop index and you have to
make sure that it processes for the loop to terminate. You array
size is apparently tracked in 'ct'. The loop searching for an
element is pretty simple and just determines for each element
whether it is different to the current value. If it is not, the
loop terminates and provides an indication on whether it terminated
because all array elements were examined or a duplicate was found.
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

[cdg]

I am not exactly sure of how you would write what you had suggested. But
I had considered this approach(below) . Could you suggest corrections, since
it does not work correctly.
And I would think that this is a simple algorithm, but seems more
complicated than some other looping problems. And I am using the book
"Starting Out with C++" and not very experienced. Also, I have not started
using vectors, these are not in the book.

do
{
"statements "

for(n=n-n; n=100?n=100:n<( n+1); n++) //n-n for zero
{
if(array[n] != var_name)
{
array[n] == var_name;
break;
}
if(array[n] == var_name)
n--;
}
}
while(n<100);

[Dietmar Kuehl]

cdg wrote:

I am not exactly sure of how you would write what you had suggested.
Well, each line in my description can be translated to a single
C++ line performing the described task. Of course, finding a
matching element may result in multiple lines if you don't want
(or don't know how) to use the 'std::find()' algorithm.
Could you suggest corrections, since it does not work correctly.
Proceed in separate steps and do what I stated before: you shall
become clear what your variables are used for. Use each variable
for exactly one task and for each task only one variable. If you
don't use 'std::vector' but an array of elements, you need to
maintain the number of elements currently in the array. To locate
a potential element within the array, you need a current index
being processed plus, of course, the value you are seeking. In
addition you might want to replace the literal "100" with named
constant to easily modify the array size.
do
{
"statements "
I guess that "statements " refers to the operations obtaining
the content of the variable "var_name". ..? What type has this
variable? Some types can be compared using the equality operator
but do not yield what you might intent. In particular, arrays of
'char' cannot be compared with "==", while 'std::string's can.
for(n=n-n; n=100?n=100:n<( n+1); n++) //n-n for zero
{
if(array[n] != var_name)
{
array[n] == var_name;
break;
}
if(array[n] == var_name)
n--;
}

Do as I have suggested:
- First try to locate the element within the existing array in a
suitable loop.
- Then, outside this loop, determine whether an element could be
located. If it wasn't just add the element to your array and
increase your element count.
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

[cdg]

I`ll try to describe exactly what is needed for the algorithm.
This is a function that receives "unsigned integers". Then these go thru
some processing steps. And result in "integers" within a certain range (0 to
100). Then they are to be placed in an array without any duplications.
However, the integers will have duplicates. So, these cannot be put into the
array if the value is already in the array. Also, the order cannot be
changed from the initial placement in the array.
So the outside loop must allow for repeated loops beyond the max size of
the array because there may be duplicates. And the iside loop has to two
different steps.
1.One is looping thru the previous placed values comparing each with this
new processed value to check for duplicates. If it isn`t a duplicate it is
placed in the array. If it is, it continues to the next value which will
come from the outside loop. And this contiunues until the max array size
(100) is reached.
2., The other is stopping when the max size of the array is reached.
And so far I have not been able to figure this out. It is the most
difficult looping that I have ever done. Or it sure seems so.
And I didn`t think I would get many responses because looping seems like
such an easy programming task.

[Neil Cerutti]

On 2006-02-24, cdg <an****@anywher e.com> wrote:

I`ll try to describe exactly what is needed for the algorithm. This is a function that receives "unsigned integers". Then these go
thru some processing steps. And result in "integers" within a
certain range (0 to 100). Then they are to be placed in an array
without any duplications. However, the integers will have
duplicates. So, these cannot be put into the array if the value is
already in the array. Also, the order cannot be changed from the
initial placement in the array.
Well, that's an unfortunate combination of requirements, since it
means you cannot use the many nice containers and algorithms designed
to make this problem easier, for example std::set, std::sort,
std::set_inters ection.

Use a 100-bool sized scratch space, seperate from your main array, to
keep track of which numbers you've got already. This will be small and
fast.

bool entered[100] = {0};

while (loop)
{
int next = get_number();
if (entered[next])
{
// Oops, we already got that number.
} else {
entered[next] = true;
// Add the number to my array.
}
// etc...
}
So the outside loop must allow for repeated loops beyond the max
size of the array because there may be duplicates. And the iside
loop has to two different steps. 1.One is looping thru the previous placed values comparing each with
this new processed value to check for duplicates. If it isn`t a
duplicate it is placed in the array. If it is, it continues to the
next value which will come from the outside loop. And this
contiunues until the max array size (100) is reached.

2., The other is stopping when the max size of the array is reached.
And so far I have not been able to figure this out. It is the most
difficult looping that I have ever done. Or it sure seems so. And I
didn`t think I would get many responses because looping seems like
such an easy programming task.

Could you be more high-level in your description, please? What is
you're doing? Perhaps there's a better way, and you don't need these
strange loops at all.

--
Neil Cerutti
You've got to take the sour with the bitter. --Samuel Goldwyn

[Daniel T.]

In article <sl************ **********@FIAD 06.norwich.edu> ,
Neil Cerutti <le*******@emai l.com> wrote:

On 2006-02-24, cdg <an****@anywher e.com> wrote:

I`ll try to describe exactly what is needed for the algorithm.

This is a function that receives "unsigned integers". Then these go
thru some processing steps. And result in "integers" within a
certain range (0 to 100). Then they are to be placed in an array
without any duplications. However, the integers will have
duplicates. So, these cannot be put into the array if the value is
already in the array. Also, the order cannot be changed from the
initial placement in the array.

Well, that's an unfortunate combination of requirements, since it
means you cannot use the many nice containers and algorithms designed
to make this problem easier, for example std::set, std::sort,
std::set_inters ection.

Yes you can. Here is the solution using "many nice containers and
algorithms"

struct already_encount ered {
set<unsigned> s;
bool operator()( unsigned i ) {
bool result = false;
if ( s.find( i ) != s.end() )
result = true;
else
s.insert( i );
return result;
}
};

template < typename BiIt, typename OutIt >
void fn( BiIt begin, BiIt end, OutIt result )
{
// process orig: for example
transform( begin, end, begin, bind2nd( modulus<unsigne d>(), 100 ) );

// remove duplicates
remove_copy_if( begin, end, result, already_encount ered() );
}

// example of use
int main()
{
srand( time( 0 ) );
vector<unsigned > orig( 1000 );
generate( orig.begin(), orig.end(), &rand );

deque<unsigned> vec;
fn( orig.begin(), orig.end(), back_inserter( vec ) );

copy( vec.begin(), vec.end(),
ostream_iterato r<unsigned>( cout, " " ) );
cout << '\n';
cout << vec.size();
}


--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Dietmar Kuehl]

cdg wrote:
[lengthy description]

I think I understood these requirements right from the start except
that the type of your elements wasn't specified. However, this is no
big deal. Here is my rather abbreviated description of the problem:

Input: a [conceptually infinite] sequence of unsigned integers in
the range 0-100.
Output: an array with 100 different values in the range 0-100 where
elements is in the same position as the first corresponding value
in the input.

The algorithm you described for this problem may not be the most
efficient (the most efficient one would use a second array recording
Boolean values indicating whether the corresponding value is already
present in the array) but effectively work: store each value in the
array the first time it occurred and stop this process as soon as a
sufficient number of elements was received.

And so far I have not been able to figure this out. It is the most
difficult looping that I have ever done. Or it sure seems so.

Your problem is not at all with the looping! Do as I advised in my
previous reply: write down (e.g. on an old-fashioned piece of paper)
the names of the variables and their use. Maybe add a drawing
representing a partially filled array and manually process the
algorithm to figure out what kind of data you need (actually, I even
mentioned it before). Then split the problem into the loops I also
already mentioned, none of which is rather complicated! Just because
you need nested loops to solve this problem (at least with the
approach you have chosen) doesn't mean this has to be complex: you
can simply consider the inner loop to do a specific task, namely to
locate a specific value or return an indication that it is not
present (of course, if the inner loop actually determines the correct
position of the value, i.e. the position of the existing value if
present or the next position not yet filled, you can simply assign
to the corresponding position...).
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

[cdg]

This is what I have found will work. All of the program details are not
included here. But it should show the steps involved. Thanks for your post,
and I`ll look over them more later to see if there is better approach than
this, when using just arrays.

int i(0); // fills the array with values (0 to 100) in order
int array[100] = {0};
int n(0);
bool test;

for(i=0; i<100; i++) // fills the array with values (0 to 100) in order
{
array[i] = i;
}

int ct(1); //starts the counter outside of the while loop
while(ct<100)
{

"other statements are here"

n = 0; //starts the counter outside of the for loop
for(n=0; n<ct; n++)
{
if(array[n]==var_name)
{
test = true;
break;
}
else
continue;
}

if(test == true)
break;
else
{
array[ct-1] = var_name;
ct++;
}
}

[Neil Cerutti]

On 2006-02-24, Daniel T. <po********@ear thlink.net> wrote:

In article <sl************ **********@FIAD 06.norwich.edu> ,
Neil Cerutti <le*******@emai l.com> wrote:

On 2006-02-24, cdg <an****@anywher e.com> wrote:

> I`ll try to describe exactly what is needed for the algorithm.

> This is a function that receives "unsigned integers". Then these go
> thru some processing steps. And result in "integers" within a
> certain range (0 to 100). Then they are to be placed in an array
> without any duplications. However, the integers will have
> duplicates. So, these cannot be put into the array if the value is
> already in the array. Also, the order cannot be changed from the
> initial placement in the array.

Well, that's an unfortunate combination of requirements, since it
means you cannot use the many nice containers and algorithms designed
to make this problem easier, for example std::set, std::sort,
std::set_inters ection.

Yes you can. Here is the solution using "many nice containers and
algorithms"

Right. I should have been more specific, i.e., you can't use them
directly as your data structure.

I quite liked your sample code, except for building up a new set
containing the same old elements every time you add a new element. But
perhaps that's the safest way to go, and at only 100 elements it's
probably fast enough.

--
Neil Cerutti