A soln to this:
1. Get the two sets, set A having n_A elements and B
having n_B elements.
2. Compute the sum of all elements in set B (the
subset ), say sum_B.
3. Compute the sum of the first n_B elements in A i.e
A[0] to A[n_B - 1]. If sum matches sum_B, need to
look more and compare each element with B. This has
been optimised with binary search (log(n) instead of n
operations). If sum does not match, go ahead and
calculate sum though A[1] to A[n_B - 1 + 1] and so on.
I have tried to make it as efficient as possible.
--Chandan
/*********************FIND_PATTERN*********************/
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
int find_match(int*, int, int*, int);
void quicksort(int*, int, int);
int partition(int*, int, int, int);
int main()
{
int A[MAXSIZE], B[MAXSIZE];
int i, j, sum, sum_B, match, n_A, n_B;
/* Take the inputs from the user */
printf("No of elements in A:");
scanf("%d", &n_A);
printf("No of elements in B:");
scanf("%d", &n_B);
if (n_B > n_A) {
printf("B has to be a subset\n");
return 1;
}
printf("Enter the entries in A:\n");
for (i = 0; i < n_A; i++)
scanf("%d", &A[i]);
printf("Enter the entries in B:\n");
for (i = 0; i < n_B; i++)
scanf("%d", &B[i]);
sum_B = 0;
for (i = 0; i < n_B; i++)
sum_B += B[i];
/*
* Using quicksort to sort the set B so that we
* can search it using binary search.
*/
quicksort(B, 0, n_B - 1);
i = 0;
match = FALSE;
while (i <= n_A - n_B) {
sum = 0;
for (j = i; j < i + n_B; j++) {
sum += A[j];
}
/* I dive into matching individuals only if sum
matches */
if (sum == sum_B) {
match = find_match(A, i, B, n_B);
/*
* If successful, I can skip all elements till
* end of pattern i.e index + n_B
*/
if (match == TRUE) {
printf("Found match at index %d!!\n", i);
i += n_B;
} else {
i += 1;
}
} else {
i += 1;
}
}
if (match == FALSE)
printf("Sorry !!\n");
return 0;
}
int find_match( int *A, int index_A, int *B, int n_B)
{
/* Track variables used in binary search */
int i, low, mid, high;
/*
* Allocate a flag array. This will be needed when
we have
* multiple occurence of a number in set B.
Initially all
* the bits are set to 0. When a number from A is
found in
* B, then the corresponding bit is set. Consider
the eg.
*
* A = {4,4,4,8,0,1} B = {8,8,4,0,0}
*
* Here, searching for 4 alone will not help us.
Hence, we
* need to identify each instance. At every
instance we come
* across, we will flag the lowest unfilled index it
appears
* in.
*/
int lowest_index;
int flag[n_B];
for (i = 0; i < n_B; i++) {
flag[i] = 0;
}
for (i = 0; i < n_B; i++) {
low = 0;
high = n_B - 1;
lowest_index = -1;
/* Binary search details !! */
while (low <= high) {
mid = (low + high)/2;
if (A[index_A + i] == B[mid] && flag[mid] == 0)
{
lowest_index = mid;
/*
* Need to find if there is an occurence of
* A[index_A + i] in the left sub tree
*/
high = mid - 1;
continue;
}
if (A[index_A + i] < B[mid])
high = mid - 1;
else
low = mid + 1;
}
if (lowest_index != -1)
flag[lowest_index] = 1;
}
for (i = 0; i < n_B; i++) {
if (flag[i] == 0)
return FALSE;
}
return TRUE;
}
/* Quick sort gory details start */
int partition(int *B, int left, int right, int
pivotIndex)
{
int i, pivotValue, temp, storeIndex;
pivotValue = B[pivotIndex];
temp = B[pivotIndex];
B[pivotIndex] = B[right];
B[right] = temp;
storeIndex = left;
for (i = left; i < right; i++) {
if (B[i] < pivotValue) {
if (i != storeIndex) {
temp = B[storeIndex];
B[storeIndex] = B[i];
B[i] = temp;
}
storeIndex += 1;
}
}
/* Move pivot to its final place */
temp = B[right];
B[right] = B[storeIndex];
B[storeIndex] = temp;
return storeIndex;
}
void quicksort(int *B, int left, int right)
{
int pivotNewIndex;
if (right > left) {
/* select a pivot value a[pivotIndex] */
pivotNewIndex = partition(B, left, right, left);
quicksort(B, left, pivotNewIndex-1);
quicksort(B, pivotNewIndex+1, right);
}
}
/*************************END**************************/
--- Junkie <[EMAIL PROTECTED]> wrote:
> Find if a given set B is a subset of another
> larger set A, such that all elements are of B appear
> together in A (may not be in same order).
>
> That is if B is such a subset of A then output
> should be the location in A where the first element
> matches from B. Else print "Not a Subset".
>
> For example-
> a. A={1,5,100,6,2,9,0,4,10}
> B={2,6,100,9}
> output= 3 (i.e. third position from left)
>
> b. A=same as above
> B={5,6,2,0}
> output= "Not a subset"
> ========================
> The whole joy of going to Heaven depends upon the
> miseries and sorrows of those who are sent to Hell
> �... ___________
> ,�� o`�, /__/ _/\_ ____/\
> ```)�(��� | | | | | | | || |l����|
> �,.-��� �,.-�~�~�-.,� `��-. :�� �~�~�-..,�
>
__________________________________
Do you Yahoo!?
Yahoo! Mail Address AutoComplete - You start. We finish.
http://promotions.yahoo.com/new_mail
------------------------ Yahoo! Groups Sponsor --------------------~-->
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/EbFolB/TM
--------------------------------------------------------------------~->
To unsubscribe, send a blank message to <mailto:[EMAIL PROTECTED]>.
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/c-prog/
<*> To unsubscribe from this group, send an email to:
[EMAIL PROTECTED]
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
