#include <iostream>
#include <vector>
#include <map>

#define DEBUG_OUTPUT 0

struct DependsKey
{
    int column;
    std::vector< int > dependantColumns;

    void Print() const
    {
      char buffer[2] = " ";
       for ( std::vector< int >::const_iterator it = dependantColumns.begin(); it != dependantColumns.end(); ++it )
       {
           buffer[0] = 'A' + *it;
           std::cout << buffer;
       }
       buffer[0] = 'A' + column;
       std::cout << " --> " << buffer;

    }
};


void FillDependsTable( std::vector< DependsKey > & dep, int column, int columnCount )
{
   unsigned long columns = 1;
   unsigned long target = 0;
   for ( int i = 0; i < columnCount; ++i )
   {
      target |= 1 << i;
   }
   DependsKey k;
   k.column = column;
   
   for ( ; columns < target; ++columns )
   {
      if ( columns & ( 1 << column ) )
      {
         continue;
      }
      k.dependantColumns.clear();
      for ( int i = 0; i < columnCount; ++i )
      {
         if ( i != column && (columns & ( 1 << i ) ) )
         {
             k.dependantColumns.push_back( i );
         }
      }
      dep.push_back( k );
   }
}

bool CheckDependency( DependsKey const & dependency, std::map< std::pair< int, int >, int > const & table, int attributeCount, int tuppleCount )
{
   #if DEBUG_OUTPUT
   std::cout << "Checking dependency ";
   dependency.Print();
   std::cout << std::endl;
   #endif

   typedef std::vector< std::pair< int, std::vector< int > > > FoundVector;
   FoundVector foundPairs;
   for ( int t = 0; t < tuppleCount; ++t )
   {
      int value = table.find( std::pair< int, int >( t, dependency.column ) )->second;
      std::vector< int > keys;
      for ( int i = 0; i < dependency.dependantColumns.size(); ++i )
      {
          keys.push_back( table.find( std::pair< int, int >( t, dependency.dependantColumns[ i ] ) )->second );
      }

      for ( FoundVector::iterator it = foundPairs.begin(); it != foundPairs.end(); ++it )
      {
          bool isCurrent = true;
          for ( int i = 0; isCurrent && i < dependency.dependantColumns.size(); ++i )
          {
             isCurrent &= it->second[ i ] == keys[ i ];
          }
          if ( isCurrent && value != it->first )
          {
             #if DEBUG_OUTPUT
             std::cout << "Dependancy failed\n";
             #endif

             return false;
          }
      }
      foundPairs.push_back( std::pair< int, std::vector< int > >( value, keys ) );
   }
   
   #if DEBUG_OUTPUT
   std::cout << "Dependancy ok\n";
   #endif
   return true;
}

std::vector< DependsKey > FindDependants( std::map< std::pair< int, int >, int > const & table, int attributeCount, int tuppleCount )
{
   std::vector< DependsKey > dependencies;
   for ( int i = 0; i < attributeCount ; ++i )
   {
      FillDependsTable( dependencies, i, attributeCount );
   }
   for ( int i = 0; i < dependencies.size(); )
   {
      if ( !CheckDependency( dependencies[ i ], table, attributeCount, tuppleCount ) )
      {
         dependencies.erase( dependencies.begin() + i );
      } else {
         ++i;
      }
   }
   return dependencies;
}

void main()
{
   std::cout << "Number of attributes: ";
   int attrs;
   std::cin >> attrs;

   std::cout << "Number of Tupples: ";
   int tupples;
   std::cin >> tupples;

   std::map< std::pair< int, int >, int > table;

   for ( int r = 0; r < tupples; ++r )
   {
      for ( int c = 0; c < attrs; ++c )
      {
         std::cout << "Tupple " << r + 1 << " attribute " << c + 1 << ": ";
         int buffer;
         std::cin >> buffer;
         table.insert( std::pair< std::pair< int, int >, int >( std::pair< int, int >( r, c ), buffer ) );
      }
   }

   std::cout << "Is this the correct relation? (1/0)\n";
   for ( int r = 0; r < tupples; ++r )
   {
      for ( int c = 0; c < attrs; ++c )
      {
          std::cout << table[ std::pair< int, int >( r, c ) ] << " ";
      }
      std::cout << std::endl;
   }
   bool correct;
   std::cin >> correct;

   if ( correct )
   {
      std::vector< DependsKey > deps = FindDependants( table, attrs, tupples );
      std::cout << "Dependencies:\n";
      for ( std::vector< DependsKey >::iterator dep = deps.begin(); dep != deps.end(); ++dep )
      {
         dep->Print();
         std::cout << std::endl;
      }
   }
}