Remove elements repeted

General FreeBASIC programming questions.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Nov 03, 2017 21:58

Hi:

1) Thank you very much everyone!

2) LOL, I've been working erroneously well all my life!

I modified the program a bit.
(I hope I did not have more errors)

Code: Select all

'lrcvs 01.10.17

'program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x

CLS
x = 30000000            'x = number of array elements
DIM s (x)AS INTEGER     'this is the main array
DIM t (x)AS INTEGER     'this is the auxiliary array

RANDOMIZE, 3
FOR n = 1 TO x
    s(n) = (INT(RND * x) + 1)     'here we write the values in the main array
    'print s(n);" ";              'show elements of auxiliary array
NEXT n

PRINT
PRINT "init array of "; x; " elements, some repeated"
PRINT

ordenar2 (s(),1,x)      'sort the elements

'******************************************************************************
'remove elements repeted

f = 1      'f = counter for the main array
c = 1      'c = counter for the auxiliary array

t(c) = s(c)

WHILE f < x
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array

'for n = 1 to c-1
'    print t(n);" ";
'next n


PRINT
PRINT "there are ";c;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB
caseih
Posts: 1647
Joined: Feb 26, 2007 5:32

Re: Remove elements repeted

Postby caseih » Nov 04, 2017 0:52

lrcvs wrote:I modified the program a bit.
(I hope I did not have more errors)

Did you compile your program with -exx to detect out-of-bounds array access? If not, why not?
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Nov 04, 2017 6:05

Hi

I have modidied the entry of values in the array to "0"

Code: Select all

'lrcvs 01.10.17

'Program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x

CLS
x = 20 '<<< elements    'x = number of array elements
DIM s (x)AS INTEGER     'This is the main array
DIM t (x)AS INTEGER     'This is the auxiliary array

RANDOMIZE, 3
FOR n = 0 TO x
    s(n) = (INT(RND * x) + 1)     'Here we write the values in the main array
    print s(n);" ";              'show elements of auxiliary array
NEXT n

print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),0,x)      'sort the elements

'******************************************************************************
'Remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
WHILE f < x   
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 0 to c
    print t(n);" ";
next n


PRINT
PRINT "There are ";c+1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Nov 05, 2017 5:00

Hi

My apologies, now is perfect.

Code: Select all

'lrcvs 01.10.17

'Program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x,z

CLS
x = 15 '<<< elements    'x = number of array elements
DIM s (x)AS INTEGER     'This is the main array
DIM t (x)AS INTEGER     'This is the auxiliary array

RANDOMIZE, 3

FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)     'Here we write the values in the main array
    print s(n);" ";              'show elements of auxiliary array
NEXT n
print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),0,x-1)      'sort the elements

'******************************************************************************
'Remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
WHILE f < x-1
   
'Here we compare an element of the main array with the following of the main array
'comparing them, if they are equal, the counter (f) of the main array advances one step, and so on
'comparing them, if they are different, we add the element of the main array to the auxiliary array and increase "c" and advance the main counter (f)
'the process is repeated until the end of the main carray
   
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 0 to c
    print t(n);" ";
next n


PRINT
PRINT "There are ";c+1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB



Regards
fxm
Posts: 10258
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Remove elements repeted

Postby fxm » Nov 05, 2017 10:52

'Dim s(n)' defines an array of n+1 elements (from index '0' to index 'n').
So to define an array of n elements:
Dim s(n-1)
or
Dim s(0 To n-1)
which is more explicit:

Code: Select all

x = 15 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'This is the main array
DIM t (0 TO x-1)AS INTEGER     'This is the auxiliary array
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Nov 05, 2017 12:19

Hi, fxm:

Thank you very much for your observation.

I modify the program with your indications.


Code: Select all

'lrcvs 01.10.17

'Program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x,z

CLS

x = 15 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'This is the main array
DIM t (0 TO x-1)AS INTEGER     'This is the auxiliary array

RANDOMIZE, 3

FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)     'Here we write the values in the main array
    print s(n);" ";              'show elements of auxiliary array
NEXT n
print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),0,x-1)      'sort the elements

'******************************************************************************
'Remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
WHILE f < x-1
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 0 to c
    print t(n);" ";
next n


PRINT
PRINT "There are ";c+1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB


Regards
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Nov 06, 2017 5:33

Hi:

Part # 2:

With the previous program, we obtain the unique elements of a list / array (or remove the repeated ones.)

Now, we show the original list / array, without the repeated elements and in the initial order.

Code: Select all

'lrcvs 01.10.17

'program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x,v,w

CLS

x = 20 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'this is the main array
DIM t (0 TO x-1)AS INTEGER     'this is the auxil_1 array
DIM r (0 TO x-1)AS INTEGER     'this is the auxil_2 array
DIM u (0 TO x-1)AS INTEGER     'this is the auxil_3 array

RANDOMIZE, 3

FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)     'here we write the values in the main array
    u(n) = s(n)
    PRINT s(n);" ";              'show elements of auxiliary array
NEXT n


PRINT
PRINT "init array of "; x; " elements, some repeated"
PRINT

ordenar2 (s(),0,x-1)      'sort the elements + auxil_2 array


'******************************************************************************
'remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
r(c) = s(c)
WHILE f < x-1
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
FOR n = 0 TO c
    PRINT t(n);" ";
NEXT n
PRINT

'clasification
FOR v = 0 TO c
    FOR w = 0 TO x-1
        IF u(w) = t(v) THEN r(w) = 1:EXIT FOR
    NEXT w
NEXT v

PRINT "there are ";c+1;" unique elements"
PRINT

'show the list / original array, without the repeated elements
FOR n = 0 TO x-1
    IF r(n) = 1 THEN PRINT u(n);" ";
NEXT n
PRINT
PRINT "list / original array, without the repeated elements"

PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
       
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB


**********************************************************************************
5 6 3 1 19 11 2 18 14 6 4 2 12 13 19 6 6 13 3 15
init array of 20 elements, some repeated

1 2 3 4 5 6 11 12 13 14 15 18 19
there are 13 unique elements

5 6 3 1 19 11 2 18 14 4 12 13 15
list / original array, without the repeated elements
***********************************************************************************

Regards
counting_pine
Site Admin
Posts: 6246
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: Remove elements repeted

Postby counting_pine » Nov 06, 2017 12:22

fxm wrote:Dim s(0 To n-1)
which is more explicit

Yes, its meaning is much more obvious.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Jul 22, 2019 5:23

Code: Select all

'lrcvs 2019.jul.21
'program to eliminate repeated elements in an array.
'1) we sort the initial array, using quicksort.
'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".
'3)It is a small improvement of the previous code, year 2017.

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER n,x

CLS
x = 110 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'this is the main array
RANDOMIZE, 3

'show elements..................................................................
PRINT "the original array"
FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)
    PRINT s(n);" ";
NEXT n

'qsort..........................................................................
ordenar2 (s(),0,x-1)

'show elements sort.............................................................
PRINT:PRINT:PRINT "show the original array sort"
FOR n = 0 TO x-1
    PRINT s(n);" ";
NEXT n

'show the original array, without the repeated elements.........................
PRINT:PRINT:PRINT "show the original array, without the repeated elements"
FOR n = 0 TO x-1
    IF s(n) <> s(n+1) THEN PRINT s(n);" ";
NEXT n

PRINT:PRINT:PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y,n
    i = inicio
    j = final
    y = s((i + j) \ 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
    END SUB


Regards
fxm
Posts: 10258
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Remove elements repeted

Postby fxm » Jul 22, 2019 5:25

The last array element must not be tested with the next, otherwise error: "out of bounds array access".

Perhaps:

Code: Select all

'show the original array, without the repeated elements.........................
PRINT:PRINT:PRINT "show the original array, without the repeated elements"
FOR n = 0 TO x-2
    IF s(n) <> s(n+1) THEN PRINT s(n);" ";
NEXT n
PRINT s(x-1);
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Remove elements repeted

Postby lrcvs » Jul 22, 2019 5:35

Hi, fxm:

As always, thank you for your observations.

Apologies
ShawnLG
Posts: 137
Joined: Dec 25, 2008 20:21

Re: Remove elements repeted

Postby ShawnLG » Sep 15, 2019 6:30

There is a much faster way to remove repeated elements from an array. You can use a hash table to remember what elements are accounted for. Hash tables run in constant time O(1) . Much faster than using quicksort.

Code: Select all

'Hashtable using quadratic probing by ShawnLG
const hNULL = -1
type hashtable
    declare constructor(byval s as integer)'Initialize hash table size
    declare destructor()
    declare sub push(key as integer)'Push key onto table
    declare function check(key as integer) as integer' Check if key is on the table
    private:
    dim as integer ptr ht
    dim as integer size
end type

constructor hashtable(byval s as integer)
    this.ht = new integer[s+1]
    for i as integer = 0 to s
        this.ht[i] = hNULL'Null the table
    next i
    this.size = s
end constructor

destructor hashtable()
    delete[] this.ht
end destructor
 
sub hashtable.push(key as integer)
    dim as integer index = key mod this.size 'hash function
    do
        if this.ht[index] = hNULL then 'check if current slot is free
            this.ht[index] = key 'put the key value in the available slot
            exit do' where done!
        else 'jump to next index
            index = (index shr 1)mod this.size 'perform quadratic hop to next slot
        end if
    loop
end sub

function hashtable.check(key as integer) as integer
    dim as integer index = key mod this.size ' hash function
    do
        if this.ht[index] = hNULL then 'check if key does not exist
            return -1
        elseif this.ht[index] = key then 'check if we found the key
            return key
        else ' jump to next index
            index = (index shr 1) mod this.size 'perform quadratic hop to next slot
        end if
    loop
end function




'lrcvs 2019.jul.21
'program to eliminate repeated elements in an array.
'1) we sort the initial array, using quicksort.
'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".
'3)It is a small improvement of the previous code, year 2017.

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER n,x

CLS
x = 110 '<<< elements    'x = number of array elements
dim as hashtable h = x * 10'need plenty of room on the hash table
DIM s (0 TO x-1)AS INTEGER     'this is the main array
RANDOMIZE, 3

'show elements..................................................................
PRINT "the original array"
FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)
    PRINT s(n);" ";
NEXT n

'qsort...........................................................................
'ordenar2 (s(),0,x-1)

'show elements sort.............................................................
'PRINT:PRINT:PRINT "show the original array sort"
'FOR n = 0 TO x-1
'    PRINT s(n);" ";
'NEXT n

'show the original array, without the repeated elements.........................
PRINT:PRINT:PRINT "show the original array, without the repeated elements"
FOR n = 0 TO x-1
    'IF s(n) <> s(n+1) THEN PRINT s(n);" ";
    if h.check(s(n)) <> s(n) then
        h.push(s(n))' keep tabs on what we have.
        print s(n);" ";
    end if
NEXT n

PRINT:PRINT:PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y,n
    i = inicio
    j = final
    y = s((i + j) \ 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB

Return to “General”

Who is online

Users browsing this forum: No registered users and 8 guests